題目敘述 My Calendar II
給定一個行事曆的class定義和行程安排的介面interface。
請完成下列function
1.建構子MyCalendarTwo() 初始化MyCalendarTwo物件
2.boolean book(int start, int end)
在行事曆加入一項新行程，起始時間為start, 結束時間為end。
該行程占用的時間是[start, end) 包含起點start, 不包含終點end。
如果新行程不會和舊行程重疊 或者 新行程只和舊行程重疊一次，
把新行程加入行事曆，並且回傳true。
如果新行程會和已知的兩個舊行程有重疊，則拒絕新行程，並且回傳false。
也就是說，每個時間點最多允許預約booking兩個行程，拒絕第三個行程。
測試範例
Example 1:
Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]
Explanation
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // 可以，沒有和任何行程重疊。
myCalendarTwo.book(50, 60); // 可以，沒有和任何行程重疊。
myCalendarTwo.book(10, 40); // 可以，從這次排程之後，[10, 20) 被預定兩個行程。
myCalendarTwo.book(5, 15); // 拒絕，因為[10, 15) 已經有兩個行程了。
myCalendarTwo.book(5, 10); // 可以，沒有和任何行程重疊。
myCalendarTwo.book(25, 55); // 可以，從這次排程之後，[25, 40) 和 [50,55) 被預定兩個行程。
範例輔助說明
示意圖 重複的檢測
演算法 每個時間點最多允許兩個行程，拒絕第三個行程。
每個行程進來先檢查是否已經有兩個行程double_bookings和當下的行程有重疊?
如果有，直接拒絕第三個行程，返回False。
接著，檢查和已知行程single_bookings是否有重疊?
如果有，就把重疊兩次的時間區域加入double_bookings。
最後，把新行程加入single_bookings，並且返回True，代表成功排入這個新行程。
程式碼 每個時間點最多允許兩個行程，拒絕第三個行程。
class MyCalendarTwo:
def __init__(self):
# 紀錄被一個行程佔據的時間區間
self.single_bookings = []
# 紀錄被兩個行程佔據的時間區間
self.double_bookings = []
def book(self, start: int, end: int) -> bool:
# 檢查新行程是否有和兩個已知的行程重疊?
# 如果有，直接拒絕新行程，返回 False。
for double_start, double_end in self.double_bookings:
if start < double_end and end > double_start:
return False
# 檢查新行程是否有和一個已知的行程重疊?
# 如果有，把重疊的時間區域記錄下來，加入double booking。
for single_start, single_end in self.single_bookings:
if start < single_end and end > single_start:
self.double_bookings.append((max(start, single_start), min(end, single_end)))
# 接受當下這個新行程，返回True
self.single_bookings.append((start, end))
return True
複雜度分析
時間複雜度: O(n^2)
總共有n個行程，每個行程需要花費O(n)時間和已知行程做檢查。
總共耗時O(n^2)
空間複雜度: O(n)
需要額外建立兩張表格，single_bookings和 double_bookings，
所需空間皆為O(n)
關鍵知識點
考的是區間如何表達，以及新增區間，檢查區間有無重疊的演算法。
強烈建議讀著一併複習相關系列題，鞏固知識點。
📆行程安排 我的行事曆I_My Calendar I_Leetcode #729
