執行結果：通過

題目 731 我的日程安排表II

實現一個程序來存放你的日程安排。如果要添加的時間內不會導致三重預訂時，則可以存儲這個新的日程安排。

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

事件能夠用一對整數?startTime?和?endTime?表示，在一個半開區間的時間?[startTime, endTime)?上預定。實數?x?的范圍為??startTime <= x < endTime。

實現?MyCalendarTwo?類：

• MyCalendarTwo()?初始化日歷對象。
• boolean book(int startTime, int endTime)?如果可以將日程安排成功添加到日歷中而不會導致三重預訂，返回?true。否則，返回?false?并且不要將該日程安排添加到日歷中。

示例 1：

輸入：
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
輸出：
[null, true, true, true, false, true, true]解釋：
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // 返回 True，能夠預定該日程。
myCalendarTwo.book(50, 60); // 返回 True，能夠預定該日程。
myCalendarTwo.book(10, 40); // 返回 True，該日程能夠被重復預定。
myCalendarTwo.book(5, 15);  // 返回 False，該日程導致了三重預定，所以不能預定。
myCalendarTwo.book(5, 10); // 返回 True，能夠預定該日程，因為它不使用已經雙重預訂的時間 10。
myCalendarTwo.book(25, 55); // 返回 True，能夠預定該日程，因為時間段 [25, 40) 將被第三個日程重復預定，時間段 [40, 50) 將被單獨預定，而時間段 [50, 55) 將被第二個日程重復預定。

提示：

• 0 <= start < end <= 109
• 最多調用?book?1000 次。

代碼以及解題思路

代碼

from sortedcontainers import SortedDict
class MyCalendarTwo:def __init__(self):self.sd = SortedDict()def book(self, startTime: int, endTime: int) -> bool:self.sd[startTime] = self.sd.get(startTime, 0) + 1self.sd[endTime] = self.sd.get(endTime, 0) - 1s = 0for v in self.sd.values():s += vif s > 2:self.sd[startTime] -= 1self.sd[endTime] += 1return Falsereturn True

解題思路：

. 初始化?SortedDict

• 在?MyCalendarTwo?類的構造函數?__init__?中，創建了一個?SortedDict?實例?self.sd。SortedDict?是一個自動保持鍵排序的字典，非常適合于按時間順序處理鍵值對。

2.?book?方法

• book?方法接受兩個參數?startTime?和?endTime，分別表示新的會議的開始時間和結束時間。
• 方法的目的是檢查并嘗試預訂這個新的會議時間段，如果在任何時間點上同時進行的會議數不超過 2 個，則返回?True，否則返回?False。

3. 處理會議的開始和結束

• 對于新的會議時間段，我們在?SortedDict?中記錄它的開始和結束。
  • 使用?self.sd[startTime] = self.sd.get(startTime, 0) + 1?增加?startTime?處的計數，表示一個新的會議開始。
  • 使用?self.sd[endTime] = self.sd.get(endTime, 0) - 1?減少?endTime?處的計數，表示一個會議結束。
• 這樣，通過遍歷?SortedDict?的值，我們可以計算出任意時間點上的會議數量。

4. 遍歷并檢查會議重疊

• 初始化一個變量?s?為 0，用于跟蹤當前時間點的會議數量。
• 遍歷?SortedDict?的值（這些值代表會議的開始和結束事件導致的計數變化），逐步更新?s。
  • 每當遇到一個開始事件（正數），將?s?增加相應的值。
  • 每當遇到一個結束事件（負數），將?s?減少相應的值。
• 在遍歷過程中，如果?s?的值在任何時間點超過了 2，表示此時有三個或更多的會議同時進行，因此不能添加新的會議時間段。
  • 如果發生這種情況，我們需要回滾對?SortedDict?的修改（即減少?startTime?的計數并增加?endTime?的計數），然后返回?False。

5. 返回結果

• 如果遍歷結束后沒有超過 2 個會議同時進行的情況，則新的會議時間段可以被成功預訂，返回?True。

總結

通過巧妙地使用?SortedDict?來記錄會議的開始和結束，并實時跟蹤任意時間點上的會議數量，這個算法高效地解決了檢查會議時間段是否可以添加的問題。這種方法避免了直接檢查所有可能的時間重疊，從而大大提高了效率。