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

更新於 發佈於 閱讀時間約 1 分鐘

題目敘述 729. My Calendar I



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

請完成下列function

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

動態測試時,最多有1000次book() function 呼叫。


示意圖 二元區間搜索樹


如果還不熟悉二元搜索樹BST,請參考這篇教學文章。

🏝用Python來實現 Binary Search Tree 二元搜尋樹


raw-image

演算法 二元區間搜索樹


我們可以把行事曆視為一顆二元區間搜索樹

每個行程視為一顆節點,裡面包含[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

留言
avatar-img
留言分享你的想法!
我來了😆😆😆剛剛一直點不進來。
小松鼠-avatar-img
發文者
2024/09/26
林燃(創作小說家)
小松鼠-avatar-img
發文者
2024/09/29
📆行程安排 我的行事曆II_My Calendar II_Leetcode #731提及了這篇文章,趕快過去看看吧!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
2024/09/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
2024/09/02
 Binary Tree Inorder Traversal 題目給定一個二元樹的根結點。 請輸出中序拜訪(In-order traversal)的拜訪序列。 中序拜訪的定義: 1.拜訪左子樹。 2.拜訪目前的節點。 3.拜訪右子樹。
Thumbnail
2024/09/02
 Binary Tree Inorder Traversal 題目給定一個二元樹的根結點。 請輸出中序拜訪(In-order traversal)的拜訪序列。 中序拜訪的定義: 1.拜訪左子樹。 2.拜訪目前的節點。 3.拜訪右子樹。
Thumbnail
看更多
你可能也想看
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
「欸!這是在哪裡買的?求連結 🥺」 誰叫你太有品味,一發就讓大家跟著剁手手? 讓你回購再回購的生活好物,是時候該介紹出場了吧! 「開箱你的美好生活」現正召喚各路好物的開箱使者 🤩
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
題目已經給了依照起點升序排列好的區間陣列。 接下來新插入一個區間,插入後如果和原本的區間重疊,請把他們合併,要求我們輸出插入後的結果。 這是一個線性掃苗,所需時間為O(n)的演算法。 題目已經幫我們排序好區間順序,我們只要接著依序檢查區間、(假如有重疊的話)合併區間。
Thumbnail
題目已經給了依照起點升序排列好的區間陣列。 接下來新插入一個區間,插入後如果和原本的區間重疊,請把他們合併,要求我們輸出插入後的結果。 這是一個線性掃苗,所需時間為O(n)的演算法。 題目已經幫我們排序好區間順序,我們只要接著依序檢查區間、(假如有重疊的話)合併區間。
Thumbnail
題目敘述 題目會給我們一個定義好的類別和function介面,要求我們實作建構子和ping() function來滿足指定的需求。 RecentCounter類別的建構子 建構子應該初始化來電紀錄,內容為空(零筆資料) int ping(int t) t代表來電時刻,單位是毫秒m
Thumbnail
題目敘述 題目會給我們一個定義好的類別和function介面,要求我們實作建構子和ping() function來滿足指定的需求。 RecentCounter類別的建構子 建構子應該初始化來電紀錄,內容為空(零筆資料) int ping(int t) t代表來電時刻,單位是毫秒m
Thumbnail
題目敘述 題目會給定一個輸入陣列intervals,陣列元素都是一組pair, intervals[i] = [starti, endi],分別代表區間的起點,和區間的終點。 請問我們最少要刪除幾個區間,才能讓剩下的區間彼此都不重疊? 題目的原文敘述 測試範例 Example 1:
Thumbnail
題目敘述 題目會給定一個輸入陣列intervals,陣列元素都是一組pair, intervals[i] = [starti, endi],分別代表區間的起點,和區間的終點。 請問我們最少要刪除幾個區間,才能讓剩下的區間彼此都不重疊? 題目的原文敘述 測試範例 Example 1:
Thumbnail
題目敘述 題目會給我們一個輸入陣列prerequisites,每個pair代表兩個課程之間的先修關係,和課程總數numCourses。 題目問我們這組課程表是否能依照順序修完所有的課程? 如果可以,返回True。 如果不行,代表有擋修形成死結,無法依照順序修完所有的課程,返回False。
Thumbnail
題目敘述 題目會給我們一個輸入陣列prerequisites,每個pair代表兩個課程之間的先修關係,和課程總數numCourses。 題目問我們這組課程表是否能依照順序修完所有的課程? 如果可以,返回True。 如果不行,代表有擋修形成死結,無法依照順序修完所有的課程,返回False。
Thumbnail
題目會定義一組類別和介面,要求我們實做餐廳訂位報號系統。 SeatManager(int n) : 初始化餐廳最多有n個座位,n 最少是1 int reserve() : 要求返回最小的可讓客人入座的空座位編號。 void unreserve(int seatNumber) : 取消訂位,這個座位歸
Thumbnail
題目會定義一組類別和介面,要求我們實做餐廳訂位報號系統。 SeatManager(int n) : 初始化餐廳最多有n個座位,n 最少是1 int reserve() : 要求返回最小的可讓客人入座的空座位編號。 void unreserve(int seatNumber) : 取消訂位,這個座位歸
Thumbnail
題目會給定一組已經規定好的介面interface,要求我們實作HashSet這種資料結構。也就是一般數學和程式語言中所說的"集合"。
Thumbnail
題目會給定一組已經規定好的介面interface,要求我們實作HashSet這種資料結構。也就是一般數學和程式語言中所說的"集合"。
Thumbnail
寫日記自省✔️ 每天解完一題Hacker Rank題目(今天寫了兩題)✔️
Thumbnail
寫日記自省✔️ 每天解完一題Hacker Rank題目(今天寫了兩題)✔️
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News