解題說明
Interval List Intersections
題目描述：給定兩個由已排序、不相交區間所組成的列表 firstList 和 secondList，求兩個列表的所有交集（重疊部分），並回傳結果陣列。若 firstList = [[0,2],[5,10]]，secondList = [[1,5],[8,12]]，則交集為 [[1,2],[5,5],[8,10]]。
解題思路：使用雙指針分別指向 firstList[i] 和 secondList[j]。對於當前兩個區間 a = firstList[i]、b = secondList[j]：
- 計算交集：
lo = max(a[0], b[0])，hi = min(a[1], b[1])。 - 若
lo <= hi，代表兩個區間有重疊，將[lo, hi]加入結果。 - 移動指針：end 值較小的那一側向後移動（因為那個區間不可能再與另一側的後續區間產生新的、更靠前的交集）。若
a[1] <= b[1]則i++，否則j++。
重複直到其中一個指針越界，時間複雜度為 O(m + n)。
C++ 解法
複雜度分析
時間複雜度：O(m + n) — 每次迴圈至少有一個指針前進，兩個指針最多各移動 m 和 n 步，總計 O(m + n)。
空間複雜度：O(1) — 不計輸出結果的空間，只使用兩個指針變數。輸出最多包含 O(m + n) 個交集區間。
虛擬碼
Function intervalIntersection(firstList, secondList):
result = []
i = 0, j = 0
While i < len(firstList) and j < len(secondList):
a = firstList[i], b = secondList[j]
lo = max(a.start, b.start)
hi = min(a.end, b.end)
If lo <= hi:
Append [lo, hi] to result
If a.end <= b.end:
i = i + 1 // firstList 的當前區間已耗盡
Else:
j = j + 1 // secondList 的當前區間已耗盡
Return result其他解法
排序合併（不適用此題）：此題兩個列表已保證有序且不相交，因此無需額外排序。若輸入為無序的混合區間，則先合併後排序，再用掃描線找交集，時間複雜度為 O((m + n) log(m + n))。
事件掃描線 O((m + n) log(m + n))：將所有區間的 start 和 end 轉為帶有 +1/-1 標記的事件，排序後掃描。當覆蓋計數等於 2 時，當前區段即為交集。邏輯較複雜，但可推廣至多個列表同時求交集的情境。
二分搜尋 O(m log n 或 n log m)：對 firstList 中每個區間，在 secondList 中用二分搜尋找可能重疊的區間範圍。適用於 m << n 的不對稱情況，但常數較大，不如雙指針直觀。
延伸思考
- 若輸入不保證各自不相交（即每個列表內部也可能有重疊），如何先將列表內部合併區間（Merge Intervals）後再求交集？
- 若有 k 個已排序不相交的區間列表，如何高效求所有列表的共同交集？能否用 Priority Queue 達到 O(N log k) 的解法？
- 如何計算兩個列表的聯集（Union），而非交集？合併策略應如何調整？