題幹與適用場景
實作日程類別，book(start, end) 不重疊時回傳 true 並保存，否則回傳 false。區間採半開語意且 start < end；[10, 20) 與 [20, 30) 可相鄰。題目考察排序結構、邊界、插入時機與複雜度。
面試官考察點
重點是能把重疊條件寫成可證明邏輯：新區間只需檢查按起點排序的前驅與後繼。強回答會比較線性掃描、平衡樹與排序陣列，並指出多執行緒或持久化服務需要原子性與鎖。
回答前需要釐清的問題
- 時間是整數還是時間戳，可否為負？
- 是否保證
start < end，非法輸入如何處理？ - 是否嚴格半開，端點相等能否相鄰？
- 預約量與時間範圍多大，是否需要取消或查詢？
- 這是單執行緒記憶體題，還是跨行程持久化並行？
30 秒回答框架
我會用依 start 排序的有序映射。對 [s, e) 找第一個起點不小於 s 的後繼；若後繼 start < e 就重疊。再檢查前驅，若前驅 end > s 就重疊。都不衝突才插入。半開區間讓 end == s 或 next.start == e 可相鄰。查找與插入 O(log n)，空間 O(n)。
分步深入解答
第一步：定義重疊條件
[a, b) 與 [c, d) 重疊當且僅當 a < d && c < b。按起點排序後，檢查直接前驅與後繼即可，因為更遠區間更早結束或更晚開始。
第二步：選擇有序結構
平衡樹或 Java TreeMap 支援前驅後繼；排序陣列查找快但中間插入 O(n)；線性掃描為 O(n)。依預約規模與操作比例選擇。
第三步：實作檢查與插入
先查後繼、再查前驅，無衝突後才寫入。不要先插入再回滾，避免例外或並行看見中間狀態。
boolean book(int start, int end) {
if (start >= end) return false;
var next = events.ceilingEntry(start);
if (next != null && next.getKey() < end) return false;
var prev = events.floorEntry(start);
if (prev != null && prev.getValue() > start) return false;
events.put(start, end);
return true;
}第四步：證明邊界正確
next.start == end 與 prev.end == start 都不重疊。相同 start 不能覆蓋舊區間，因此後繼檢查會拒絕相交 end。注意整數溢位。
第五步：說明複雜度
平衡樹查找前驅、後繼與插入皆 O(log n)，空間 O(n)。排序陣列查找 O(log n) 但插入 O(n)；線性掃描較簡單但不適合大量預約。
第六步：擴充並行與持久化
單機在檢查與插入外加同一把鎖。跨行程服務使用資料庫交易、唯一約束或範圍鎖；快取不能承擔最終衝突判定。
設計取捨與邊界
半開還是閉區間
半開區間自然表示相鄰時段，長度為 end - start，也減少邊界重複。業務若用閉區間，必須重新定義粒度。
TreeMap 還是區間樹
只新增且不允許重疊時，前驅後繼足夠。加入重疊查詢、取消或範圍統計後，可考慮區間樹或資料庫索引。
落地計畫與證據
測試矩陣
覆蓋首個區間、完全包含、部分重疊、相鄰端點、相同 start、非法空區間、大數值與重複請求。每次接受後核對有序不變量。
生產化邊界
多實例時定義交易隔離、衝突錯誤碼、重試冪等鍵與時區規範，並用並行壓測驗證持久化約束。
常見誤區與追問
誤區：只檢查後繼
新區間可能覆蓋前驅尾部，必須檢查前驅 end。
誤區：端點相等也算衝突
半開區間允許 [10, 20) 與 [20, 30) 相鄰，使用嚴格比較。
誤區：先插入再發現衝突
檢查與寫入要是邏輯原子步驟，避免破壞不變量。
追問：如何允許兩次重疊？
維護活動區間計數或掃描線，問題變成最大重疊數約束。
追問：如何處理並行預約？
單機加鎖；多實例使用交易、範圍鎖或可串行化寫入，不能只靠記憶體。