題目敘述 729. My Calendar I
給定一個行事曆的class定義和行程安排的介面interface。
請完成下列function1.建構子MyCalendar() 初始化MyCalendar物件
2.boolean book(int start, int end)
在行事曆加入一項新行程，起始時間為start, 結束時間為end。
該行程占用的時間是[start, end) 包含起點start, 不包含終點end。
如果新行程不會和舊行程重疊，把新行程加入行事曆，並且回傳true。
如果新行程會和舊行程重疊，則拒絕新行程，並且回傳false。
測試範例
Example 1:
Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]
Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // 可以 返回True
myCalendar.book(15, 25); // [15, 25) 已經和前一個行程[10, 20)重疊，返回False
myCalendar.book(20, 30); // 可以 [20, 30) 和 [10, 20) 沒有重疊，可以加入行事曆。返回True
約束條件
Constraints:
0 <= start < end <= 10^9
0 <= 起點時間 < 終點時間<= 十億
- At most
1000calls will be made tobook.
動態測試時，最多有1000次book() function 呼叫。
示意圖 二元區間搜索樹
如果還不熟悉二元搜索樹BST，請參考這篇教學文章。
🏝用Python來實現 Binary Search Tree 二元搜尋樹
演算法 二元區間搜索樹
我們可以把行事曆視為一顆二元區間搜索樹。
每個行程視為一顆節點，裡面包含[start, end)資訊。
任何比較晚的行程插入時，都放在右子樹，並且返回True。
任何比較早的行程插入時，都放在左子樹，並且返回True。
如果新行程和舊有的行程有重疊，則return False，代表行程有重疊，拒絕新行程。
程式碼 二元區間搜索樹
class TreeNode():
def __init__(self, start, end):
self.start = start
self.end = end
self.left = None
self.right = None
class MyCalendar:
def __init__(self):
self.root = None
def book(self, start: int, end: int) -> bool:
if not self.root:
self.root = TreeNode(start, end)
return True
else:
return self.insert(start, end, self.root)
def insert(self, start, end, node):
if start >= node.end:
if node.right:
return self.insert(start, end, node.right)
else:
node.right = TreeNode(start, end)
return True
elif end <= node.start:
if node.left:
return self.insert(start, end, node.left)
else:
node.left = TreeNode(start, end)
return True
else:
return False
複雜度分析
時間複雜度: O( n log n)
總共n個行程，每個行程插入二元區間搜索樹時耗費O(log n)時間。
總共需時O( n log n)
空間複雜度: O(n)
總共n個行程，每個行程視為一顆節點Node，放入二元區間搜索樹。
二元區間搜索樹最多會有O(n)顆節點。
