解題說明
My Calendar II
題目描述：實作一個日曆類別，支援 book(start, end) 方法。允許雙重預訂（兩個事件重疊），但不允許三重預訂（三個事件在同一時間點重疊）。如果新事件不會導致三重預訂就加入並回傳 true，否則回傳 false。
解題思路：維護兩個列表：bookings 存所有已預訂的區間，overlaps 存所有已經雙重預訂的區間（即兩個已有事件重疊的部分）。新事件 [start, end) 加入前，先檢查它是否與 overlaps 中的任何區間重疊——如果是，就會形成三重預訂，回傳 false。若不會三重預訂，則計算新事件與每個已有 booking 的重疊部分加入 overlaps，最後將新事件加入 bookings。
C++ 解法
複雜度分析
時間複雜度：O(n) 每次 book — 需遍歷 overlaps 和 bookings，各自最多 n 個元素。
空間複雜度：O(n) — 存儲 bookings 和 overlaps 列表。
虛擬碼
1. Maintain two lists: bookings (all events), overlaps (double-booked intervals)
2. book(start, end):
a. For each interval [s, e] in overlaps:
- If [start, end) overlaps with [s, e): return false (would cause triple booking)
b. For each interval [s, e] in bookings:
- If [start, end) overlaps with [s, e):
- Add intersection [max(start,s), min(end,e)) to overlaps
c. Add [start, end) to bookings
d. Return true其他解法
差分陣列 / 事件掃描線 O(n log n)：用 std::map<int, int> 作為差分陣列，start 處 +1，end 處 -1。每次 book 前先暫時加入新事件的差分，然後從左到右掃描計算前綴和。如果任何時刻前綴和 >= 3，則回滾並回傳 false；否則保留。保證正確性但每次 book 需要 O(n log n) 掃描。
線段樹 + 座標壓縮：用線段樹維護每個時間點的預訂次數，支援區間加 1 和區間最大值查詢。每次 book 前查詢 [start, end) 的最大預訂數，若 < 2 則區間加 1。時間 O(log C)，但實作複雜度較高。
延伸思考
- 如果要支援取消預訂，如何修改 overlaps 列表？
- 如何推廣到 My Calendar K（最多允許 k 重預訂）？
- 差分陣列方法和列表方法在什麼操作模式下各有優勢？