【729. 我的日程安排錶 I】

來源：力扣（LeetCode）

描述：

實現一個 MyCalendar 類來存放你的日程安排。如果要添加的日程安排不會造成 重複預訂 ，則可以存儲這個新的日程安排。

當兩個日程安排有一些時間上的交叉時（例如兩個日程安排都在同一時間內），就會產生 重複預訂 。

日程可以用一對整數 start 和 end 錶示，這裏的時間是半開區間，即 [start, end), 實數 x 的範圍為， start <= x < end 。

實現 MyCalendar 類：

• MyCalendar() 初始化日曆對象。
• boolean book(int start, int end) 如果可以將日程安排成功添加到日曆中而不會導致重複預訂，返回 true 。否則，返回 false 並且不要將該日程安排添加到日曆中。

示例：

輸入：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
輸出：
[null, true, false, true]

解釋：
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False ，這個日程安排不能添加到日曆中，因為時間 15 已經被另一個日程安排預訂了。
myCalendar.book(20, 30); // return True ，這個日程安排可以添加到日曆中，因為第一個日程安排預訂的每個時間都小於 20 ，且不包含時間 20 。

提示：

• 0 <= start < end <= 10⁹
• 每個測試用例，調用 book 方法的次數最多不超過 1000 次。

方法一：直接遍曆

我們記錄下所有已經預訂的課程安排區間，當我們預訂新的區間 [start,end) 時，此時檢查當前已經預訂的每個日程安排是否與新日程安排沖突。若不沖突，則可以添加新的日程安排。

• 對於兩個區間 [s1, e1)和 [s2, e2)，如果二者沒有交集，則此時應當滿足 s1 ≥ e2 或者 s2 ≥ e1，這就意味著如果滿足 s1 < e2 並且 s2 < e1 ，則兩者會產生交集。

代碼：

class MyCalendar {
    
private:
    vector<pair<int, int>> booked;
public:
    MyCalendar() {
    

    }
public:
    bool book(int start, int end) {
    
        for (auto &[l, r] : booked) {
    
            if (l < end && start < r) {
    
                return false;
            }
        }
        booked.emplace_back(start, end);
        return true;
    }
};

執行用時：80 ms, 在所有 C++ 提交中擊敗了77.49%的用戶
內存消耗：36.6 MB, 在所有 C++ 提交中擊敗了97.08%的用戶
複雜度分析
時間複雜度：O(n²), 其中 n 錶示日程安排的數量。由於每次在進行預訂時，都需要遍曆所有已經預訂的行程安排。
空間複雜度： O(n)，其中 n 錶示日程安排的數量。需要保存所有已經預訂的行程。

方法二：二分查找

如果我們按時間順序維護日程安排，則可以通過二分查找日程安排的情况來檢查新日程安排是否可以預訂，若可以預訂則在排序結構中更新插入日程安排。

• 需要一個數據結構能够保持元素排序和支持快速插入，可以用 TreeSet 來構建。對於給定的區間 [start,end)，我們每次查找起點大於等於 end 的第一個區間 [ l1, r1 )，同時緊挨著 [ l1, r1) 的前一個區間為 [ l2, r2)，此時如果滿足 r2 ≤ start < end ≤ l1 ，則該區間可以預訂。

代碼：

class MyCalendar {
    
private:
    set<pair<int, int>> booked;
public:
    MyCalendar() {
    

    }
public:
    bool book(int start, int end) {
    
        auto it = booked.lower_bound({
    end, 0});
        if (it == booked.begin() || (--it)->second <= start) {
    
            booked.emplace(start, end);
            return true;
        }
        return false;
    }
};

執行用時：64 ms, 在所有 C++ 提交中擊敗了98.77%的用戶
內存消耗：37.9 MB, 在所有 C++ 提交中擊敗了53.51%的用戶
複雜度分析
時間複雜度： O(nlogn), 其中 n 錶示日程安排的數量。由於每次在進行預訂時，都需要進行二分查找，需要的時間為 O(logn)。
空間複雜度： O(n)，其中 n 錶示日程安排的數量。需要保存所有已經預訂的行程。

方法三：線段樹

代碼：

class MyCalendar {
    
    unordered_set<int> tree, lazy;

public:
    bool query(int start, int end, int l, int r, int idx) {
    
        if (r < start || end < l) {
    
            return false;
        }
        /* 如果該區間已被預訂，則直接返回 */
        if (lazy.count(idx)) {
    
            return true;
        }
        if (start <= l && r <= end) {
    
            return tree.count(idx);
        }
        int mid = (l + r) >> 1;
        return query(start, end, l, mid, 2 * idx) ||
               query(start, end, mid + 1, r, 2 * idx + 1);
    }

    void update(int start, int end, int l, int r, int idx) {
    
        if (r < start || end < l) {
    
            return;
        }
        if (start <= l && r <= end) {
    
            tree.emplace(idx);
            lazy.emplace(idx);
        } else {
    
            int mid = (l + r) >> 1;
            update(start, end, l, mid, 2 * idx);
            update(start, end, mid + 1, r, 2 * idx + 1);
            tree.emplace(idx);
            if (lazy.count(2 * idx) && lazy.count(2 * idx + 1)) {
    
                lazy.emplace(idx);
            }
        }
    }

    bool book(int start, int end) {
    
        if (query(start, end - 1, 0, 1e9, 1)) {
    
            return false;
        }
        update(start, end - 1, 0, 1e9, 1);
        return true;
    }
};

執行用時：476 ms, 在所有 C++ 提交中擊敗了5.03%的用戶
內存消耗：171.4 MB, 在所有 C++ 提交中擊敗了7.53%的用戶