題目與適用情境
給定一組未排序的閉區間 intervals，每個元素為 [start, end]，且 start <= end。請合併所有重疊區間，回傳一個依起點遞增排列、兩兩不重疊的新串列，並保持覆蓋範圍不變。本題使用閉區間語意，因此 [1, 4] 與 [4, 5] 共用點 4，應合併為 [1, 5]。函式不得修改輸入。
例如：
輸入：[[8, 10], [1, 3], [2, 6], [15, 18]]
輸出：[[1, 6], [8, 10], [15, 18]]輸入可以是空串列，也可能包含重複區間、負數端點、零長度區間和完全巢狀的區間。基礎題假設每個元素都恰好有兩個合法整數，不在合併函式內處理格式錯誤。這題適用於一般軟體工程師的程式設計面試，核心能力是把任意順序轉換成能做區域決策的順序，再證明這個貪心決策不會漏掉跨區間的合併。
面試官考察重點
第一個訊號是候選人會不會先定義區間語意。閉區間、半開區間，以及「相鄰也算可合併」都會直接改變判斷條件。只寫 start < current_end 而沒有說明語意，在共用端點的測試案例上可能答錯。
第二個訊號是能否解釋排序的作用。排序後，下一個區間的起點不會小於目前起點；如果它已經大於目前合併區間的終點，所有更後面的起點只會更大，目前區間便可以安全輸出。好的回答會說清楚這個「可以定稿」的理由，而非只背「排序後掃一次」。
第三個訊號是巢狀區間的處理。合併 [1, 10] 與 [2, 3] 時，終點必須取 max(10, 3)；直接覆寫成 3 會遺失覆蓋範圍。鏈式重疊也必須和正在擴張的合併結果比較，而非只比較相鄰的原始區間。
最後還會檢查程式契約、複雜度和驗證方式。排序通常決定 O(n log n) 時間；本實作以新的排序串列和結果串列換取輸入不可變，總空間為 O(n)。測試不能只涵蓋標準範例，還要驗證輸入沒有被修改、輸出已排序且兩兩不重疊，並用慢速基準實作做隨機差異測試。
回答前需要釐清的問題
- 區間是閉區間還是半開區間？共用端點是否合併？ 本題是閉區間，所以條件為
nextstart <= currentend。若業務把相鄰區間視為分開，條件改為嚴格小於；半開區間[a, b)還要另外確認「連續但不重疊」是否需要合併。 - 輸入是否已依起點排序？ 已排序時可直接線性掃描，時間降為
O(n)；未排序輸入需要排序，或採用依賴端點範圍的特殊方法。 - 允許修改輸入嗎？ 允許時可以原地排序並用寫入指標壓縮結果；不允許時必須複製，或使用回傳新串列的排序函式。
- 端點範圍是否很小且都是整數？ 任意可比較數值使用比較排序最直接；若座標只來自很小的整數域，可以考慮 bucket 或差分陣列，但空間會依賴座標範圍，而非區間數量。
- 只做一次離線合併，還是區間持續到達？ 依起點排序的串流可以邊讀邊輸出；任意順序的串流無法安全提前定稿，因為未來可能出現一個更早、更長的區間，把既有結果連接起來。
- 輸出只需要邊界，還是要保留區間 metadata？ 合併邊界不代表標籤、權限或價格也能無損合併；若每段帶有 metadata，必須另外定義聚合規則。
30 秒回答架構
「我先確認這些是閉區間，共用端點也算重疊，而且不能修改輸入。我會複製並依起點、終點遞增排序，接著維護一個目前的合併區間。若下一個起點小於等於目前終點，就把目前終點擴張為兩者終點的最大值；否則目前區間不可能再和後面的區間相交，可以加入答案並開始新區間。掃描結束後再加入最後一個區間。排序是 O(n log n)，掃描是 O(n)，新的排序串列和輸出共用 O(n) 空間。正確性來自排序後的不變量：已輸出的區間都已定稿，目前區間恰好覆蓋尚未輸出的最後一個連通部分。」
分步深入解答
一個直接做法是反覆尋找任意一對重疊區間，合併後從頭掃描，直到沒有變化。它容易寫成雙層迴圈，但一次合併可能讓新區間和先前看過的區間再次重疊，因此需要多輪掃描，最壞會到 O(n²) 甚至更差。這個方法適合當成小規模測試 oracle，卻不適合當主解法。
排序把全域問題變成單向掃描。先依 (start, end) 遞增排列。維護 current = [currentstart, currentend]，代表已處理但尚未輸出的最後一個合併部分。對下一個 [start, end]：
- 若
start <= currentend，兩個閉區間重疊，把currentend更新為max(current_end, end)。 - 若
start > current_end，目前區間與下一個區間之間已有空隙。由於後續起點都不小於start，之後也不可能再碰到current；先輸出current，再用新區間開始。
掃描過程維護三個不變量：
- 已輸出區間依起點遞增排列、兩兩不重疊，而且之後不會再改變。
- 已輸出區間與
current的聯集，恰好等於所有已處理輸入區間的聯集。 current是已處理區間中最後一個最大合併部分，也是唯一可能與下一個區間重疊的部分。
初始時只處理排序後的第一個區間，三項都成立。遇到重疊時，只擴張最後部分的右端點，不改變覆蓋範圍；遇到空隙時，排序保證任何未來起點都在 current_end 之後，因此輸出是安全的。歸納到掃描結束，再輸出 current，就得到覆蓋範圍相同且無法繼續合併的結果。
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
if not intervals:
return []
ordered = sorted((start, end) for start, end in intervals)
merged: list[list[int]] = []
current_start, current_end = ordered[0]
for start, end in ordered[1:]:
if start <= current_end:
current_end = max(current_end, end)
else:
merged.append([current_start, current_end])
current_start, current_end = start, end
merged.append([current_start, current_end])
return mergedsorted() 會建立新的排序串列，tuple 解包也不會改寫原本的子串列，因此函式符合輸入不可變。比較排序為 O(n log n)，掃描為 O(n)，總時間為 O(n log n)。排序副本和最壞包含 n 個區間的輸出都是線性規模，所以包含輸出時空間為 O(n)。若輸入已排序，跳過排序後時間為 O(n)；若允許原地修改，可原地排序並用寫入指標重複使用輸入空間，但仍要說明排序實作可能使用的 stack 或暫存緩衝區。
驗證時先涵蓋空輸入、單一區間、完全分離、共用端點、完全巢狀、重複區間、負數端點和鏈式重疊。例如 [[1, 2], [2, 3], [3, 4]] 必須得到 [[1, 4]]，它能抓出只和前一個原始區間比較的錯誤。再保留輸入的深層複本，呼叫後確認沒有變化。最後產生小型隨機區間，以「反覆合併任意重疊對」的慢速演算法當 oracle；本文程式已對 10,000 組固定 seed 的隨機輸入完成差異驗證。
對任意數值和比較模型，排序加掃描是清楚的通用答案。若 n 很小，反覆合併可能更短，效能差異也沒有實際意義；若輸入原本就有序，線性掃描更簡單；若端點是很小的有界整數域，可以用 bucket 或差分方法換取依賴座標範圍的時間與空間。面試中應先用限制條件證明特殊方案值得採用。
高品質示範回答
「我會先把邊界說清楚：輸入是未排序的閉區間，共用端點要合併，回傳新串列而且不修改原資料。像 [1, 4] 和 [4, 5] 的判斷必須使用小於等於。
暴力做法可以不斷找重疊對再重新掃描，但合併後的新區間可能和前面元素產生新的重疊，最壞要做很多輪。我會先依起點排序，之後只保留一個尚未定稿的區間；下一個起點落在它的終點以內時，用兩個終點的最大值擴張，否則把它寫入結果並開始下一段。
關鍵不是相鄰元素本身，而是目前所有鏈式重疊後的結果。排序保證一旦下一個起點超過目前終點，後面所有起點也都會超過，所以目前結果可以永久定稿。因此已輸出部分始終有序且互不重疊，目前部分則覆蓋已處理輸入的最後一個合併部分。
程式會使用 sorted() 建立副本，空輸入直接回傳。時間是排序的 O(n log n) 加線性掃描，空間是排序副本和輸出的 O(n)。我會重點測共用端點、巢狀、重複、負數和鏈式重疊，再以慢速兩兩合併作為 oracle 做隨機差異測試，同時斷言輸入沒有改變。」
常見錯誤
- 沒有定義端點語意就寫
<或<=→ 共用端點案例的結果取決於契約 → 先確認閉區間、半開區間和連續區間是否合併，再選擇判斷條件。 - 依原始順序掃描 → 原本重疊的區間可能相隔很遠，已輸出結果還可能被未來區間連接 → 先依起點排序，或明確確認輸入已排序。
- 只比較相鄰原始區間 →
[1, 10]、[2, 3]、[9, 12]的第三段需要和擴張後的[1, 10]比較 → 始終比較最後一個合併結果。 - 重疊時直接寫
currentend = end→ 被包含的區間會縮短目前覆蓋範圍 → 使用max(currentend, end)。 - 漏掉最後一次加入 → 迴圈只在遇到空隙時輸出，最後一段會消失 → 迴圈結束後統一加入
current。 - 空輸入仍讀取第一個元素 → 發生索引越界 → 排序和初始化前回傳空串列。
- 承諾不修改輸入卻呼叫原地排序 → 呼叫端看到順序改變，甚至子串列被重複使用後繼續變動 → 使用
sorted()與新的結果物件，或把可變行為寫進契約。 - 只測固定輸出 → 鏈式重疊、輸入變動或邊界條件仍可能錯誤 → 加入性質檢查和隨機差異 oracle。
- 無條件宣稱無法快於
O(n log n)→ 已排序輸入或小整數座標域可以避開比較排序 → 把下界限定在未排序、任意可比較端點的模型。
追問及應對
追問 1：如果共用端點不算重疊，程式要怎麼改？
把合併條件從 start <= currentend 改為 start < currentend。但要先確認業務語意：對閉區間而言，共用端點在數學上有交集；若產品仍要求分開，實際契約是「只合併正長度重疊」。對半開區間 [a, b)，[1, 4) 與 [4, 5) 不重疊，是否把連續區段合併又是另一個選擇。
追問 2：輸入已依起點排序，而且允許修改，如何降低額外空間？
跳過排序，並用寫入指標把合併結果寫回輸入前綴。讀取指標掃描新區間；重疊時更新寫入位置的終點，不重疊時遞增寫入指標並複製新區間。最後回傳前綴長度或前綴 view。掃描是 O(n)，不含回傳結果的額外空間是 O(1)，代價是破壞原輸入。
追問 3：區間依起點排序後持續到達，能否串流輸出？
可以。只保留一個 current；遇到起點超過目前終點的區間時輸出 current，再開始新區間，串流結束時輸出最後一段。工作記憶體為 O(1)，不含輸出。若到達順序任意，未來區間可能把兩段連接起來，不能安全提前輸出；需要緩衝、外部排序或維護動態區間資料結構。
追問 4：有一億個區間，記憶體放不下怎麼辦？
先依起點做外部排序：每批在記憶體內排序並寫出有序 run，再執行多路合併。合併串流本身已依起點排序，可以同時執行相同的單區間合併狀態，不必先產生完整的全域排序檔。CPU 比較工作仍是 O(n log n) 量級，主要新增成本是磁碟 I/O 和暫存空間。
追問 5：每個區間還帶有價格或權限標籤，可以直接合併嗎？
只有邊界可以按目前演算法求聯集。若重疊區段的標籤不同，合併成單一標籤會遺失資訊。需要先定義輸出是標籤集合、優先級最高的標籤，還是把端點切成標籤不變的最小分段；最後一種通常要改用掃描線事件，而非單純回傳區間聯集。