主題: 學習筆記
TypeScript 合併區間：用排序建立可證明的不變量
從排序、單次掃描到不變量，完整推導 TypeScript 合併區間解法，並釐清輸入不可變與 O(n log n) 複雜度。
這份解答是在 AI 輔助下完成，但我不想只留下「程式跑得動」的結果。我重新確認了每個判斷成立的原因、輸入是否被修改，以及排序為什麼主導整體複雜度。真正能帶進面試的不是記住程式碼，而是能說清楚那個讓單次掃描成立的不變量。
題目
給定一組區間 [start, end]，合併所有重疊或端點相接的區間。輸入順序不固定，函式不得修改原始輸入。
例如：
[[1, 3], [2, 6], [8, 10], [10, 12]]
→ [[1, 6], [8, 12]]先排序，才能只比較最後一段
如果區間沒有排序，當前區間可能與結果中任何一段重疊。先依 start 遞增排序後，每次處理新區間時，結果陣列 merged 都維持兩個條件：
- 已依起點排序。
- 彼此不重疊，而且已完整合併所有看過的區間。
因此只需要比較 merged 的最後一段。若 currentStart <= lastEnd，兩段重疊或接壤；新的終點取兩者較大值。若 currentStart > lastEnd，因為後面的起點只會更大，當前區間不可能再與更早的結果重疊，可以直接新增。
這就是核心不變量。並不是因為「前面已經比較過」所以可以略過，而是排序加上 merged 已完全合併，保證最後一段是唯一可能與目前區間相交的候選。
TypeScript 解法
type Interval = readonly [start: number, end: number];
function mergeIntervals(intervals: readonly Interval[]): Interval[] {
if (intervals.length === 0) return [];
const sorted = [...intervals].sort(([a], [b]) => a - b);
const merged: Interval[] = [sorted[0]];
for (let index = 1; index < sorted.length; index += 1) {
const current = sorted[index];
const lastIndex = merged.length - 1;
const last = merged[lastIndex];
if (current[0] <= last[1]) {
merged[lastIndex] = [last[0], Math.max(last[1], current[1])];
} else {
merged.push(current);
}
}
return merged;
}sort() 會原地修改陣列，所以先用 [...intervals] 複製外層陣列。區間型別也使用 readonly tuple，讓函式不能意外改寫呼叫端傳入的端點。合併時直接建立新 tuple，而不是修改既有區間。
最小驗證
單純 console.log() 只能讓人目視結果；assertion 才會在結果錯誤時直接失敗。
import assert from "node:assert/strict";
const input: Interval[] = [[1, 3], [2, 6], [8, 10], [10, 12]];
const snapshot = input.map((interval) => [...interval]);
assert.deepStrictEqual(mergeIntervals(input), [[1, 6], [8, 12]]);
assert.deepStrictEqual(input, snapshot);
assert.deepStrictEqual(mergeIntervals([]), []);
assert.deepStrictEqual(mergeIntervals([[1, 4], [2, 3]]), [[1, 4]]);最後一個案例特別重要：如果合併時直接把終點設成 current[1]，[1, 4] 會錯誤縮短成 [1, 3]，因此必須使用 Math.max()。
複雜度與 JavaScript 的現實
面試中通常把比較排序視為 O(n log n)，後續掃描是 O(n)，因此總時間為 O(n log n)，額外空間為 O(n)。這不是 O(n²)：巢狀迴圈並不是判斷複雜度的必要條件，排序演算法也不能只用程式表面的一行來猜。
更精確地說，ECMAScript 並未保證 Array.prototype.sort() 的時間與空間複雜度；MDN 也明確指出它取決於 JavaScript engine。O(n log n) 是這題常用的面試分析模型，而不是語言規格承諾。
常見陷阱
- 直接對輸入呼叫
sort()，違反「不得修改輸入」。 - 使用
<而非<=，漏掉端點相接也要合併的需求。 - 合併時沒有取最大終點，導致較大的既有區間被縮短。
- 只說程式跑過，卻無法描述排序後的不變量。
- 把函式呼叫或
console.log()當成測試，沒有對預期結果做 assertion。
我學到什麼
- 排序的價值不是方便閱讀，而是把「可能與誰重疊」縮小成最後一段。
- 複雜度要分開計算排序與掃描，再取主導項。
readonly型別與複製陣列能把「不修改輸入」變成可檢查的契約。- AI 可以協助產生起點，但我仍需要自行驗證不變量、邊界案例與複雜度。
外部參考連結
- MDN：Array.prototype.sort()：確認
sort()會修改原陣列，以及複雜度由實作決定。 - TypeScript Handbook：readonly tuple types：用型別表達區間端點不應被修改。
- Node.js：assert.deepStrictEqual()：用可失敗的 assertion 驗證結果與輸入不變性。