題幹與適用場景
請實作一個區間集合，支援 add([l,r))、remove([l,r))、contains(x) 和 overlaps([l,r))。插入相鄰或重疊區間時要自動合併，刪除可以把區間拆開；說明開閉邊界、空區間和複雜度。
這道題考察有序集合、不變量和邊界處理。Python bisect 文件說明二分只負責尋找插入位置，列表插入本身仍可能是 O(n)；因此候選人要說明資料規模和是否需要樹結構，而不是直接聲稱所有操作都是 O(log n)。
面試官考察點
第一項是能否固定半開區間語意並處理相鄰區間。第二項是插入和刪除時只掃描可能相交的鄰居，而不是每次遍歷全部區間。第三項是能否根據規模選擇陣列、平衡樹或專用區間樹，並給出不變量證明。
回答前需要釐清的問題
- 區間是閉、開還是半開？ 預設使用
[l,r)，這樣相鄰[0,1)和[1,2)不重疊。 - 端點允許浮點數嗎？ 預設是可比較的整數；浮點需要說明精度和 NaN 規則。
- 是否要求合併相鄰區間？ 預設相鄰也合併，以保持規範化表示。
- 資料規模和讀寫比例是多少？ 小規模可用有序陣列，大規模考慮平衡樹或區間樹。
- 刪除不存在的範圍如何處理？ 預設冪等，不報錯，只保留實際存在的部分。
30 秒回答框架
「我先固定半開區間和規範化不變量：區間按左端點排序、互不重疊且不相鄰。add 用二分找到第一個可能相交的區間，向右合併重疊或相鄰項；remove 找到相交區間後保留左右剩餘部分。contains 看前一個區間，overlaps 用第一個右端點大於查詢左端點的區間判斷。陣列實作搜尋 O(log n) 但搬移是 O(n)；若規模大，換成平衡樹或區間樹。」
分步驟深入解答
第一步：定義規範化不變量
始終保存有序、互不重疊且不相鄰的半開區間 [l,r)，並保證 l < r。空區間不進入集合。規範化後，任意點最多屬於一個區間，插入和刪除可以只圍繞局部鄰居操作。
第二步：選擇儲存結構
若區間數量不超過幾千且寫入不密集，有序陣列簡單可靠；二分搜尋找到位置，插入和刪除搬移陣列元素。若寫入和查詢都很大，使用帶有序鍵的平衡樹；若需要統計覆蓋數量或最大重疊深度，再考慮增強區間樹。
第三步：實作插入的鄰居定位
用 bisect_left 找到第一個左端點不小於 l 的位置，再檢查它左側一個區間，因為左側區間可能延伸到 l。從這個位置向右掃描，直到下一個區間的左端點嚴格大於目前合併右端點；相鄰區間也納入合併。
add(l, r):
i = first index with start >= l, then i = max(0, i - 1)
while i < len(intervals) and intervals[i].end >= l:
l = min(l, intervals[i].start)
r = max(r, intervals[i].end)
delete intervals[i]
insert [l, r) at i第四步：實作刪除和拆分
找到第一個可能與 [l,r) 相交的區間，逐個處理到左端點不小於 r 為止。對每個區間保留 [start,l) 和 [r,end) 中仍非空的部分。因為輸入集合已經規範化，刪除不會產生需要再次合併的相鄰區間。
第五步：實作點查詢和區間查詢
contains(x) 找到最後一個 start <= x 的區間，判斷 x < end。overlaps([l,r)) 找到第一個 end > l 的區間，若其 start < r 則相交；空查詢區間直接返回 false。所有比較都遵循半開邊界。
第六步：證明正確性
插入迴圈只刪除與新範圍重疊或相鄰的區間，並把它們的並集替換為一個區間，因此不會漏掉覆蓋範圍。刪除只移除交集並保留兩側差集。排序和不相鄰不變量在每次操作後恢復，查詢只需檢查一個候選鄰居即可。
第七步：分析複雜度
陣列的二分定位是 O(log n)，但移動和合併刪除可能是 O(n)，其中 n 是區間數。單次操作掃描 k 個相鄰區間時還要付出 O(k)。平衡樹能把定位和局部更新降到 O(log n + k)，但實作和記憶體開銷更高。不要把二分搜尋複雜度當成完整操作複雜度。
第八步：設計邊界測試
測試空集合、空區間、相鄰合併、完全包含、部分重疊、跨越多個區間、刪除中間部分、刪除端點、負數、重複操作和大範圍查詢。隨機產生操作，與逐點布林陣列模型對拍，驗證集合的覆蓋結果一致。
設計取捨與邊界
取捨一：半開還是閉區間
半開區間讓相鄰範圍自然拼接，長度是 r-l，適合時間和陣列下標。若業務使用閉區間，必須把相鄰判定、長度和整數溢位規則統一改變，不能只改比較符號。
取捨二：陣列還是平衡樹
陣列程式碼短、快取友善，適合讀多寫少和中小規模。平衡樹適合大量插入刪除，但需要穩定的有序鍵和迭代器失效規則。先用實際 n、寫入比例和延遲預算做選擇。
取捨三：是否合併相鄰範圍
合併相鄰範圍能減少項目數量並簡化查詢；若業務必須保留原始段邊界，就應儲存來源元資料，不能只用一個並集區間替換歷史。
失敗演練與演進計畫
演練一：大量相鄰插入
按相反順序插入 10,000 個相鄰區間，驗證最終只剩一個規範化區間，且沒有遺漏端點。觀察陣列搬移成本，判斷是否需要樹結構。
演練二：隨機插入和刪除
隨機產生 add/remove/contains/overlaps，與逐點模型對拍。重點檢查刪除把一個區間拆成兩段後，後續插入能正確合併。
演練三：邊界和異常輸入
測試 l == r、l > r、極大整數和 NaN。明確空區間返回、反向區間報錯或交換，以及浮點輸入是否被拒絕。
常見誤區與追問
誤區一：把相鄰和重疊混為一談
半開 [0,1) 與 [1,2) 沒有交集，但題目若要求規範化相鄰區間仍可合併。要分別定義交集和合併條件。
誤區二：只檢查右側鄰居
左側區間可能跨過新範圍左端點。二分後必須回看一個前驅。
誤區三：刪除後留下空區間
保留左右差集時過濾 start >= end 的結果，否則 contains 會出現幽靈命中。
誤區四：聲稱 bisect 讓插入 O(log n)
Python 文件明確指出列表插入搬移是 O(n)。應完整說明搜尋、搬移和掃描成本。
誤區五：忽略浮點邊界
NaN 不滿足正常排序關係，近似相等也會讓相鄰判斷不穩定。若業務允許浮點，先定義規範化精度。
誤區六：沒有保留來源資訊
如果區間代表權限、預訂或帳期，簡單合併可能丟失來源。此時需要額外元資料或選擇不合併的表示。