程式設計面試：如何求兩組已排序區間的交集？

題幹與適用場景

給定兩個陣列 A 與 B。每個元素是閉區間 [start, end]，兩個陣列都依 start 非遞減排序，且同一陣列內沒有重疊區間。回傳所有同時落在 A 與 B 的區間，結果也要依起點排序。

例如 A = [[1,5],[10,14]]、B = [[2,3],[4,12]]，交集是 [[2,3],[4,5],[10,12]]。端點相等算有交集；因此 [1,2] 與 [2,4] 的交集是 [2,2]。

面試官考察點

面試官要看你能否把「兩個已排序序列」轉成雙指標掃描，而不是把所有區間兩兩比較。強回答會先定義閉區間語義，再用 max(start) 與 min(end) 計算當前交集，最後說明為什麼只前進結束較早的那一邊。

回答前需要澄清的問題

1. 區間是閉區間還是半開區間？這會改變端點相等時是否輸出。
2. 每組是否保證已排序且組內不重疊？若不保證，需先排序，或先合併每組區間。
3. 輸入是否可能為空、包含單點區間或 start > end？這決定驗證與錯誤處理。
4. 是否要求保留重疊長度為零的單點？本題閉區間要求保留。

30 秒回答框架

「我用兩個指標 i、j 從兩組第一個區間開始。當前交集左端是兩個起點的較大值，右端是兩個終點的較小值；只要左端不大於右端就輸出。接著移動終點較小的區間，因為它已不可能再和另一個當前或更後面的區間產生新的交集。每個指標最多走完整個陣列，所以時間是 O(m+n)，額外空間不含輸出為 O(1)。」

分步驟深入解答

第一步：固定區間語義

將每個區間視為 [start,end]。若 left = max(A[i].start, B[j].start)、right = min(A[i].end, B[j].end)，左端不大於右端就代表存在交集，兩端相等是合法單點。

第二步：推導指標移動

若 A[i].end 小於 B[j].end，A[i] 在時間軸上先結束。由於 B[j] 之後的區間起點不會更早，A[i] 不可能再與 B[j+1] 或更後區間重疊，因此只能 i++。B[j].end 小於 A[i].end 時對稱地 j++。

第三步：處理同時結束

若兩個終點相等，兩邊都已經沒有剩餘範圍可和下一個區間重疊，必須同時遞增 i、j。只遞增一邊會再次拿已結束的區間比較，可能漏掉下一段或增加無效步驟。

第四步：寫出可執行骨架

function intersect(A: number[][], B: number[][]): number[][] {
  const out: number[][] = [];
  let i = 0;
  let j = 0;

  while (i < A.length && j < B.length) {
    const left = Math.max(A[i][0], B[j][0]);
    const right = Math.min(A[i][1], B[j][1]);
    if (left <= right) out.push([left, right]);

    if (A[i][1] < B[j][1]) i++;
    else if (B[j][1] < A[i][1]) j++;
    else { i++; j++; }
  }
  return out;
}

第五步：用不變量說明正確性

每次迴圈開始時，i、j 指向尚未證明不可能產生交集的最早區間。計算出的 [left,right] 是這兩個區間唯一可能的交集；若有交集就輸出。移動較早結束的一側後，所有被跳過的配對都因時間順序不可能相交，因此不會漏解。

第六步：分析複雜度與輸入防禦

兩個指標只會前進，最多 m+n 次，時間複雜度 O(m+n)。輸出陣列不計入額外工作空間時是 O(1)；若計入輸出，空間是 O(k)。若契約不保證排序或有效端點，應先驗證或排序，不能直接套用線性解法。

高品質示範回答

我先確認區間是閉區間、兩組都已依起點排序且組內不重疊。掃描 A[i] 與 B[j] 時，交集就是起點取大、終點取小；在閉區間下左端不大於右端都要輸出。之後我移動終點較小的指標，因為它已經結束，後面的區間起點只會更晚，不可能補回新的交集；兩個終點相等則同時移動。這樣每個區間只被處理一次，時間 O(m+n)。我會測空陣列、沒有交集、端點相等、單點區間、完全包含與多段連續交集。

常見錯誤

• 錯誤表現 → 只在左端小於右端時輸出 → 失敗原因：閉區間的單點交集被漏掉 → 修正方法：先確認契約，左端不大於右端時也要輸出。
• 錯誤表現 → 每個 A 區間掃過所有 B 區間 → 失敗原因：忽略排序，時間退化為 O(mn) → 修正方法：維護兩個單調指標。
• 錯誤表現 → 永遠只遞增 i → 失敗原因：B[j] 可能先結束，導致重複比較或漏解 → 修正方法：比較兩個終點，較小者前進，同值時兩者前進。
• 錯誤表現 → 輸入未排序仍宣稱線性 → 失敗原因：指標移動的證明失效 → 修正方法：補上排序或每組先合併的前置步驟。

追問及應對

如果區間改成半開區間 [start,end)，哪些條件要改？

交集存在的條件改成左端小於右端；[1,2) 與 [2,4) 不產生單點交集。指標移動的終點比較仍可沿用，但要在答案中明確說明端點語義。

如果每組區間沒有排序且可能重疊，還能做到 O(m+n) 嗎？

不能直接做到。先各自依起點排序，並合併組內重疊區間，再做雙指標；成本至少包含排序的 O(m log m+n log n)，之後掃描仍是線性。

如果要回傳交集長度總和，而不是區間列表呢？

仍用相同掃描；每次有交集就累加 right-left 加上端點是否包含的修正。對閉區間的整數時間軸，需先定義長度是幾何長度還是點數，不能直接混用。

如果輸入是兩個串流，不能回看已讀區間呢？

只要每個串流仍按起點排序，雙指標狀態可以保留當前區間與下一筆讀取位置。輸出一段交集後丟棄已結束的一側；若要處理回溯或亂序，就需要緩衝與不同設計。