📆行程安排 我的行事曆I_My Calendar I_Leetcode #729

Behnam Norouzi on Unsplash

題目敘述 729. My Calendar I

給定一個行事曆的class定義和行程安排的介面interface。

請完成下列function

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 1000 calls will be made to book.

動態測試時，最多有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)顆節點。

Reference

[1] My Calendar I - LeetCode