《日程安排》專題 · ttttt

# 《日程安排》專題《我的日程安排表》截止目前（2020-02-03）在 LeetCode 上一共有三道題，其中兩個中等難度，一個困難難度,分別是： - [729. 我的日程安排表 I](https://leetcode-cn.com/problems/my-calendar-i) - [731. 我的日程安排表 II](https://leetcode-cn.com/problems/my-calendar-ii) - [732. 我的日程安排表 III](https://leetcode-cn.com/problems/my-calendar-iii) 另外 LeetCode 上有一個類似的系列《會議室》，截止目前（2020-02-03）有兩道題目。其中一個簡單一個中等，分別是： - [252. 會議室](https://leetcode-cn.com/problems/meeting-rooms/) - [253. 會議室 II](https://leetcode-cn.com/problems/meeting-rooms-ii/) 今天我們就來攻克它們。 # 729. 我的日程安排表 I ## 題目地址 <https://leetcode-cn.com/problems/my-calendar-i> ## 題目描述實現一個 MyCalendar 類來存放你的日程安排。如果要添加的時間內沒有其他安排，則可以存儲這個新的日程安排。 MyCalendar 有一個 book(int start, int end)方法。它意味著在 start 到 end 時間內增加一個日程安排，注意，這里的時間是半開區間，即 \[start, end), 實數 x 的范圍為， start <= x < end。當兩個日程安排有一些時間上的交叉時（例如兩個日程安排都在同一時間內），就會產生重復預訂。每次調用 MyCalendar.book 方法時，如果可以將日程安排成功添加到日歷中而不會導致重復預訂，返回 true。否則，返回 false 并且不要將該日程安排添加到日歷中。請按照以下步驟調用 MyCalendar 類: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end) 示例 1: MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(15, 25); // returns false MyCalendar.book(20, 30); // returns true 解釋: 第一個日程安排可以添加到日歷中. 第二個日程安排不能添加到日歷中，因為時間 15 已經被第一個日程安排預定了。第三個日程安排可以添加到日歷中，因為第一個日程安排并不包含時間 20 。說明: 每個測試用例，調用 MyCalendar.book 函數最多不超過 100 次。調用函數 MyCalendar.book(start, end)時， start 和 end 的取值范圍為 \[0, 10^9\]。 ## 暴力法 ### 思路首先我們考慮暴力法。每插入一個元素我們都判斷其是否和已有的`所有`課程重疊。我們定一個函數`intersected(calendar, calendars)`，其中 calendar 是即將要插入的課程，calendars 是已經插入的課程。只要 calendar 和 calendars 中的任何一個課程有交叉，我們就返回 True，否則返回 False。對于兩個 calendar，我們的判斷邏輯都是一樣的。假設連個 calendar 分別是`[s1, e1]`和`[s2, e2]`。那么如果`s1 >= e2 or s2 <= e1`, 則兩個課程沒有交叉，可以預定，否則不可以。如圖，1，2，3 可以預定，剩下的不可以。 ![](https://img.kancloud.cn/2b/2b/2b2b52ed318e062c1ae06f7536af06da_1154x982.jpg) 代碼是這樣的： ``` <pre class="calibre18">``` def intersected(calendar, calendars): for [start, end] in calendars: if calendar[0] >= end or calendar[1] <= start: continue else: return True return False ``` ``` 復雜度分析： - 時間復雜度：O(N2)O(N^2)O(N2)。N 指的是日常安排的數量，對于每個新的日常安排，我們檢查新的日常安排是否發生沖突來決定是否可以預訂新的日常安排。 - 空間復雜度: O(N)O(N)O(N)。這個代碼寫出來之后整體代碼就呼之欲出了，全部代碼見下方代碼部分。 ### 代碼代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` # # @lc app=leetcode.cn id=729 lang=python3 # # [729] 我的日程安排表 I # # @lc code=start class MyCalendar: def __init__(self): self.calendars = [] def book(self, start: int, end: int) -> bool: def intersected(calendar, calendars): for [start, end] in calendars: if calendar[0] >= end or calendar[1] <= start: continue else: return True return False if intersected([start, end], self.calendars): return False self.calendars.append([start, end]) return True # Your MyCalendar object will be instantiated and called as such: # obj = MyCalendar() # param_1 = obj.book(start,end) # @lc code=end ``` ``` 實際上我們還可以換個角度，上面的思路判斷交叉部分我們考慮的是“如何不交叉”，剩下的就是交叉。我們也可以直接考慮交叉。還是上面的例子，如果兩個課程交叉，那么一定滿足`s1 < e2 and e1 > s2`。基于此，我們寫出下面的代碼。代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` # # @lc app=leetcode.cn id=729 lang=python3 # # [729] 我的日程安排表 I # # @lc code=start class MyCalendar: def __init__(self): self.calendars = [] def book(self, start: int, end: int) -> bool: for s, e in self.calendars: if start < e and end > s: return False self.calendars.append([start, end]) return True # Your MyCalendar object will be instantiated and called as such: # obj = MyCalendar() # param_1 = obj.book(start,end) # @lc code=end ``` ``` ## 二叉查找樹法 ### 思路和上面思路類似，只不過我們每次都對 calendars 進行排序，那么我們可以通過二分查找日程安排的情況來檢查新日常安排是否可以預訂。如果每次插入之前都進行一次排序，那么時間復雜度會很高。如圖，我們的\[s1,e1\], \[s2,e2\], \[s3,e3\] 是按照時間順序排好的日程安排。我們現在要插入\[s,e\],我們使用二分查找，找到要插入的位置，然后和插入位置的課程進行一次比對即可，這部分的時間復雜度是 O(logN)O(logN)O(logN)。 ![](https://img.kancloud.cn/87/89/8789868df0519ce244617137128e9347_1332x434.jpg) 我們考慮使用平衡二叉樹來維護這種動態的變化，在最差的情況時間復雜度會退化到上述的O(N2)O(N^2)O(N2)，平均情況是O(NlogN)O(NlogN)O(NlogN)，其中 N 是已預訂的日常安排數。 ![](https://img.kancloud.cn/f3/30/f330e989dcb71ec6f14cb4596f7b2b64_1216x554.jpg) ### 代碼代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` class Node: def __init__(self, start, end): self.start = start self.end = end self.left = self.right = None def insert(self, node): if node.start >= self.end: if not self.right: self.right = node return True return self.right.insert(node) elif node.end <= self.start: if not self.left: self.left = node return True return self.left.insert(node) else: return False class MyCalendar(object): def __init__(self): self.root = None def book(self, start, end): if self.root is None: self.root = Node(start, end) return True return self.root.insert(Node(start, end)) ``` ``` # 731. 我的日程安排表 II ## 題目地址 <https://leetcode-cn.com/problems/my-calendar-ii> ## 題目描述實現一個 MyCalendar 類來存放你的日程安排。如果要添加的時間內不會導致三重預訂時，則可以存儲這個新的日程安排。 MyCalendar 有一個 book(int start, int end)方法。它意味著在 start 到 end 時間內增加一個日程安排，注意，這里的時間是半開區間，即 \[start, end), 實數 x 的范圍為， start <= x < end。當三個日程安排有一些時間上的交叉時（例如三個日程安排都在同一時間內），就會產生三重預訂。每次調用 MyCalendar.book 方法時，如果可以將日程安排成功添加到日歷中而不會導致三重預訂，返回 true。否則，返回 false 并且不要將該日程安排添加到日歷中。請按照以下步驟調用 MyCalendar 類: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end) 示例： MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(50, 60); // returns true MyCalendar.book(10, 40); // returns true MyCalendar.book(5, 15); // returns false MyCalendar.book(5, 10); // returns true MyCalendar.book(25, 55); // returns true 解釋：前兩個日程安排可以添加至日歷中。第三個日程安排會導致雙重預訂，但可以添加至日歷中。第四個日程安排活動（5,15）不能添加至日歷中，因為它會導致三重預訂。第五個日程安排（5,10）可以添加至日歷中，因為它未使用已經雙重預訂的時間 10。第六個日程安排（25,55）可以添加至日歷中，因為時間 \[25,40\] 將和第三個日程安排雙重預訂；時間 \[40,50\] 將單獨預訂，時間 \[50,55）將和第二個日程安排雙重預訂。提示：每個測試用例，調用 MyCalendar.book 函數最多不超過 1000 次。調用函數 MyCalendar.book(start, end)時， start 和 end 的取值范圍為 \[0, 10^9\]。 ## 暴力法 ### 思路暴力法和上述思路類似。但是我們多維護一個數組 intersectedCalendars 用來存儲**二次預定**的日程安排。如果課程第一次沖突，我們將其加入 intersectedCalendars，如果和 intersectedCalendars 也沖突了，說明出現了三次預定，我們直接返回 False。 ### 代碼代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` class MyCalendarTwo: def __init__(self): self.calendars = [] self.intersectedCalendars = [] def book(self, start: int, end: int) -> bool: for [s, e] in self.intersectedCalendars: if start < e and end > s: return False for [s, e] in self.calendars: if start < e and end > s: self.intersectedCalendars.append([max(start, s), min(end, e)]) self.calendars.append([start, end]) return True ``` ``` ## 二叉查找樹法和上面的題目類似，我們仍然可以使用平衡二叉樹來簡化查找邏輯。具體可以參考[這個 discussion](https://leetcode.com/problems/my-calendar-ii/discuss/158747/Python-O(logN)>) 每次插入之前我們都需要進行一次判斷，判斷是否可以插入。如果不可以插入，直接返回 False，否則我們進行一次插入。插入的時候，如果和已有的相交了，我們判斷是否之前已經相交了一次，如果是返回 False，否則返回 True。關于**如何判斷是否和已有的相交**，我們可以在 node 節點增加一個字段的方式來標記，在這里我們使用 single\_overlap，True 表示產生了二次預定，False 則表示沒有產生過兩次及以上的預定。 ## 代碼代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` class Node: def __init__(self, start, end): self.start = start self.end = end self.left = None self.right = None self.single_overlap = False class MyCalendarTwo: def __init__(self): self.root = None def book(self, start, end): if not self.canInsert(start, end, self.root): return False self.root = self.insert(start, end, self.root) return True def canInsert(self, start, end, root): if not root: return True if start >= end: return True if end <= root.start: return self.canInsert(start, end, root.left) elif start >= root.end: return self.canInsert(start, end, root.right) else: if root.single_overlap: return False elif start >= root.start and end <= root.end: return True else: return self.canInsert(start, root.start, root.left) and self.canInsert(root.end, end, root.right) def insert(self, start, end, root): if not root: root = Node(start, end) return root if start >= end: return root if start >= root.end: root.right = self.insert(start, end, root.right) elif end <= root.start: root.left = self.insert(start, end, root.left) else: root.single_overlap = True a = min(root.start, start) b = max(root.start, start) c = min(root.end, end) d = max(root.end, end) root.start, root.end = b, c root.left, root.right = self.insert(a, b, root.left), self.insert(c, d, root.right) return root # Your MyCalendarTwo object will be instantiated and called as such: # obj = MyCalendarTwo() # param_1 = obj.book(start,end) ``` ``` # 732. 我的日程安排表 III ## 題目地址 <https://leetcode-cn.com/problems/my-calendar-iii/> ## 題目描述實現一個 MyCalendar 類來存放你的日程安排，你可以一直添加新的日程安排。 MyCalendar 有一個 book(int start, int end)方法。它意味著在 start 到 end 時間內增加一個日程安排，注意，這里的時間是半開區間，即 \[start, end), 實數 x 的范圍為， start <= x < end。當 K 個日程安排有一些時間上的交叉時（例如 K 個日程安排都在同一時間內），就會產生 K 次預訂。每次調用 MyCalendar.book 方法時，返回一個整數 K ，表示最大的 K 次預訂。請按照以下步驟調用 MyCalendar 類: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end) 示例 1: MyCalendarThree(); MyCalendarThree.book(10, 20); // returns 1 MyCalendarThree.book(50, 60); // returns 1 MyCalendarThree.book(10, 40); // returns 2 MyCalendarThree.book(5, 15); // returns 3 MyCalendarThree.book(5, 10); // returns 3 MyCalendarThree.book(25, 55); // returns 3 解釋: 前兩個日程安排可以預訂并且不相交，所以最大的 K 次預訂是 1。第三個日程安排\[10,40\]與第一個日程安排相交，最高的 K 次預訂為 2。其余的日程安排的最高 K 次預訂僅為 3。請注意，最后一次日程安排可能會導致局部最高 K 次預訂為 2，但答案仍然是 3，原因是從開始到最后，時間\[10,20\]，\[10,40\]和\[5,15\]仍然會導致 3 次預訂。說明: 每個測試用例，調用 MyCalendar.book 函數最多不超過 400 次。調用函數 MyCalendar.book(start, end)時， start 和 end 的取值范圍為 \[0, 10^9\]。 ## 二叉查找樹法 ### 思路我們仍然可以使用上述的平衡二叉樹的做法。只不過我們需要額外維護一個全局的最大值“k”，表示需要多少個預定。最終我們返回 k。同時每一個 node 我們都增加一個屬性 k，用來表示局部的最大值，對于每次插入，我們將 node 的 k 和全部的 k 進行比較，取出最大值即可。 ### 代碼代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` class Node(object): def __init__(self, start, end, ktime=1): self.k = ktime self.s = start self.e = end self.right = None self.left = None class MyCalendarThree(object): def __init__(self): self.root = None self.k = 0 def book(self, start, end): self.root = self.insert(self.root, start, end, 1) return self.k def insert(self, root, start, end, k): if start >= end: return root if not root: self.k = max(self.k, k) return Node(start, end, k) else: if start >= root.e: root.right = self.insert(root.right, start, end, k) return root elif end <= root.s: root.left = self.insert(root.left, start, end, k) return root else: a = min(root.s, start) b = max(root.s, start) c = min(root.e, end) d = max(root.e, end) root.left = self.insert(root.left, a, b, a == root.s and root.k or k) root.right = self.insert(root.right, c,d, d == root.e and root.k or k) root.k += k root.s = b root.e = c self.k = max(root.k, self.k) return root ``` ``` ## Count Map 法 ### 思路這個是我在看了 Discussion [\[C++\] Map Solution, beats 95%+](https://leetcode.com/problems/my-calendar-iii/discuss/176950/C%2B%2B-Map-Solution-beats-95%2B) 之后寫的解法，解法非常巧妙。我們使用一個 count map 來存儲所有的預定，對于每次插入，我們執行`count[start] += 1`和`count[end] -= 1`。 count\[t\] 表示從 t 開始到下一個 t 我們有幾個預定。因此我們需要對 count 進行排序才行。我們維護一個最大值來 cnt 來表示需要的預定數。比如預定\[1,3\]和\[5,7\]，我們產生一個預定即可： ![](https://img.kancloud.cn/fe/43/fe43ac3062c5ee5e032f9b4fc7f10bfa_1394x408.jpg) 再比如預定\[1,5\]和\[3,7\]，我們需要兩個預定： ![](https://img.kancloud.cn/3f/5e/3f5eddfc9ad0efa04e61b1f458bb4cee_1418x442.jpg) 我們可以使用紅黑樹來簡化時間復雜度，如果你使用的是 Java，可以直接使用現成的數據結構 TreeMap。我這里偷懶，每次都排序，時間復雜度會很高，但是可以 AC。讀到這里，你可能會發現：這個解法似乎更具有通用型。對于第一題我們可以判斷 cnt 是否小于等于 1，對于第二題我們可以判斷 cnt 是否小于等于 2。 > 如果你不借助紅黑樹等數據結構直接使用 count-map 法，即每次都進行一次排序，第一題和第二題可能會直接超時。 ### 代碼代碼支持 Python3: Python3 Code: ``` <pre class="calibre18">``` class MyCalendarThree: def __init__(self): self.count = dict() def book(self, start: int, end: int) -> int: self.count[start] = self.count.get(start, 0) + 1 self.count[end] = self.count.get(end, 0) - 1 cnt = 0 cur = 0 for k in sorted(self.count): cur += self.count[k] cnt = max(cnt, cur) return cnt # Your MyCalendarThree object will be instantiated and called as such: # obj = MyCalendarThree() # param_1 = obj.book(start,end) ``` ``` # 相關題目 LeetCode 上有一個類似的系列《會議室》，截止目前（2020-02-03）有兩道題目。其中一個簡單一個中等，解題思路非常類似，大家用這個解題思路嘗試一下，檢測一下自己是否已經掌握。兩道題分別是： - [252. 會議室](https://leetcode-cn.com/problems/meeting-rooms/) - [253. 會議室 II](https://leetcode-cn.com/problems/meeting-rooms-ii/) # 總結我們對 LeetCode 上的專題《我的日程安排》的三道題進行了匯總。對于區間判斷是否重疊，我們可以反向判斷，也可以正向判斷。暴力的方法是每次對所有的課程進行判斷是否重疊，這種解法可以 AC。我們也可以進一步優化，使用二叉查找樹來簡化時間復雜度。最后我們介紹了一種 Count-Map 方法來通用解決所有的問題，不僅可以完美解決這三道題，還可以擴展到《會議室》系列的兩道題。