解題說明
My Calendar I
題目描述:實作一個日曆類別 MyCalendar,支援 book(start, end) 方法。每次預訂一個半開區間 [start, end),如果與已有事件不重疊就加入並回傳 true,否則回傳 false(不做任何修改)。
解題思路:使用 C++ 的 std::map 維護已預訂的區間(key = start, value = end)。對於新的 [start, end),用 lower_bound(start) 找到第一個 start 不小於新區間起點的已有區間。如果該區間的 start < end(新區間的結束時間),則重疊。同時檢查前一個區間(如果存在)的 end 是否 > start。如果都不重疊,插入新區間。
C++ 解法
複雜度分析
時間複雜度:O(log n) 每次 book — 其中 n 為已預訂的事件數量,map 的查找和插入均為 O(log n)。
空間複雜度:O(n) — 存儲所有已預訂的區間。
虛擬碼
1. Maintain sorted map: calendar (start -> end) 2. book(start, end): a. Find iterator it = lower_bound(start) — first event with start >= new start b. If it exists and it->start < end: overlap, return false c. If it has predecessor and predecessor->end > start: overlap, return false d. Insert calendar[start] = end e. Return true
其他解法
暴力法 O(n):用陣列存所有區間,每次 book 時遍歷檢查所有已有區間是否重疊。簡單但每次操作為 O(n)。
線段樹 / 平衡 BST:使用線段樹或自平衡 BST,每次操作保證 O(log n)。功能更強大但對此題而言 std::map 已足夠且實作更簡潔。
延伸思考
- 如何擴展以支援取消預訂(cancel)操作?
- 如果允許最多 k 次重疊預訂(即 My Calendar II / III),該如何修改?
- 在大量併發預訂的場景下,如何保證線程安全?