解題說明
My Calendar III
題目描述：實作一個日曆類別，支援 book(start, end) 方法，加入事件 [start, end) 並回傳所有時間點中的最大重疊預訂數（k-booking 的最大 k 值）。
解題思路：使用差分陣列（事件掃描線）的思想。用 std::map<int, int> 記錄每個時間點的變化量：start 時刻 +1，end 時刻 -1。每次 book 後，從左到右掃描所有事件點，計算前綴和，取其最大值即為最大重疊數。map 的有序性保證了掃描的正確順序。
C++ 解法
複雜度分析
時間複雜度：O(n) 每次 book — 需遍歷 map 中所有事件點計算前綴和，n 為已記錄的不同時間點數。
空間複雜度：O(n) — map 存儲所有不同的時間點。
虛擬碼
1. Maintain sorted map: diff (time -> delta)
2. book(start, end):
a. diff[start] += 1
b. diff[end] -= 1
c. Scan all entries in diff from left to right:
- ongoing += delta
- maxK = max(maxK, ongoing)
d. Return maxK其他解法
線段樹（動態開點 + 懶標記）O(log C)：用動態開點的線段樹維護每個時間區間的最大重疊數。addRange 對 [start, end) 區間加 1，query 查詢全域最大值。每次 book 為 O(log C)（C 為值域），適合操作次數極多的場景。
排序事件列表 O(n log n)：不用 map 而用 vector 存事件點再排序。插入為 O(1)，但每次計算最大值需 O(n log n) 排序。不如 map 方法的 O(n) 掃描，因為 map 自動維持有序。
延伸思考
- 如果需要查詢特定時間區間 [l, r) 內的最大重疊數（而非全域最大），該如何實作？
- 差分陣列方法的全域掃描在操作次數很多時是否會成為瓶頸？如何用線段樹優化？
- 此問題與會議室問題（Meeting Rooms II）有何關聯？