解題說明
Remove Interval
題目描述：給定一組已排序（按起點遞增）且不重疊的區間 intervals，以及一個要移除的區間 toBeRemoved = [x, y]。移除 [x, y] 後，回傳剩餘的不重疊區間（仍需按起點排序）。
解題思路：線性掃描每個區間 [a, b]，根據與 [x, y] 的關係分三種情況處理：
- 完全不相交（在左側）：若
b <= x，則[a, b]完全在移除區間左側，直接保留。 - 完全不相交（在右側）：若
a >= y，則[a, b]完全在移除區間右側，直接保留。 - 有交集：否則有重疊，移除交集部分後可能產生零個、一個或兩個剩餘片段：
- 若
a < x，保留左側片段[a, x]。 - 若
b > y，保留右側片段[y, b]。
- 若
由於輸入區間已排序且不重疊，一次線性掃描即可完成，無需排序。
C++ 解法
複雜度分析
時間複雜度：O(n) — 對 n 個區間各做常數時間判斷，一次線性掃描完成。
空間複雜度：O(1) — 除回傳結果外，只使用常數個額外變數。回傳的結果陣列大小最多為 n+1（每個輸入區間最多裂成兩半，但移除區間只有一個，所以新增片段最多 1 個），可視為 O(n)。
虛擬碼
1. Let x = toBeRemoved[0], y = toBeRemoved[1].
2. Initialize result = [].
3. For each interval [a, b] in intervals:
a. If b <= x or a >= y:
- Append [a, b] to result (no overlap).
b. Else (overlap with [x, y]):
- If a < x: append [a, x] to result.
- If b > y: append [y, b] to result.
4. Return result.其他解法
方法一：二分搜尋定位邊界
先用二分搜尋找到 toBeRemoved 影響的第一個和最後一個區間，再對這些區間做精確裁剪，其餘直接複製。時間複雜度同為 O(n)（因為複製其他區間仍需 O(n)），但減少了不必要的逐一判斷，適合移除區間覆蓋範圍很小的情況。
方法二：差分端點排序（事件掃描） 將所有區間的端點與移除區間的端點混合排序，模擬「插入/刪除」事件，動態維護活躍區間集合。時間 O(n log n)，比直接掃描慢，但可推廣到多個移除區間的情況。
方法三：先合併再減去
先對輸入區間取聯集（本題已無重疊），再用集合差運算減去 toBeRemoved。思路抽象清晰，但需要額外的資料結構，不如直接線性掃描高效。
延伸思考
- 若需要同時移除多個區間（而非只有一個），如何修改算法？時間複雜度會如何變化？
- 若輸入區間未排序，需要先排序嗎？是否有不排序的解法？
- 本題的「裁剪有重疊的區間」邏輯在插入區間（LeetCode 57）和合併區間（LeetCode 56）中也很常見，三題的核心差異在哪裡？