解題說明
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），該如何修改？
- 在大量併發預訂的場景下，如何保證線程安全？