掃描線與區間
把每個區間的起點和終點當成事件排好，從左掃到右：會議室要幾間、行事曆怎麼合併、哪些時段重疊，都變成一次排序加一次掃描。
8
1/17
現在同時
0
最多同時
0
掃描線：排序＋事件
58
暴力：每一對
64
把 8 個區間變成 16 個事件：開始 +1、結束 −1，依時間排序（比較了 42 次）。時間相同時結束排前面：[a, b) 和 [b, c) 不算重疊。
綠色：掃描線上正在進行的區間。底部藍色：到目前為止合併出的區塊。
亮起來的是這一步執行的程式碼
function maxOverlap(intervals: [number, number][]): number { const events: [number, number][] = []; for (const [s, e] of intervals) { events.push([s, 1], [e, -1]); } // Ends (-1) sort before starts (+1) at the same time. events.sort((a, b) => a[0] - b[0] || a[1] - b[1]); let active = 0, best = 0; for (const [, delta] of events) { active += delta; best = Math.max(best, active); } return best;} function mergeIntervals(intervals: [number, number][]): [number, number][] { const sorted = [...intervals].sort((a, b) => a[0] - b[0]); const out: [number, number][] = []; for (const [s, e] of sorted) { const last = out[out.length - 1]; if (last && s <= last[1]) last[1] = Math.max(last[1], e); else out.push([s, e]); } return out;}模型假設與範圍
- Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。
什麼時候用
- 問題是關於「時段」：同一時間最多幾個、哪些重疊、合併成幾段。把開始和結束當成事件排序，掃一遍。
- 需要知道「目前有哪些」而不只是數量時，掃描時用堆積或有序集合維護正在進行的那些。
和其他主題的關係
時間與空間複雜度（Big O）
| 操作 | 平均 | 最差 |
|---|---|---|
| 掃描線：最多同時幾個、合併區間 排序佔大頭；掃描本身 O(n) | O(n log n) | O(n log n) |
| 暴力：每個起點檢查所有區間 | O(n²) | O(n²) |
| 已排序的輸入 | O(n) | O(n) |
空間：O(n)，2n 個事件
Big O 實測：n 變大時步數怎麼長
數的是：比較次數（掃描線含排序），同一組隨機區間
| Big O | n = 250 | n = 500 | n = 1,000 | n = 2,000 | 成長倍數：實測（理論） | |
|---|---|---|---|---|---|---|
| 掃描線 | O(n log n) | 4,206 | 9,398 | 20,794 | 45,528 | ×11 (×11) |
| 暴力 | O(n²) | 62,500 | 250,000 | 1,000,000 | 4,000,000 | ×64 (×64) |
和其他做法比
| n = 250 | n = 500 | n = 1,000 | n = 2,000 | |
|---|---|---|---|---|
| 掃描線（排序比較＋事件） | 4,206 | 9,398 | 20,794 | 45,528 |
| 暴力（每個起點數覆蓋它的區間） | 62,500 | 250,000 | 1,000,000 | 4,000,000 |
同一組隨機區間，兩種方法求「最多同時幾個」。n 從 250 到 2,000，暴力法的檢查變成 64 倍，掃描線只變成 11 倍。
真實世界裡的它
- 會議室要幾間（見「考題：會議室 II」）、行事曆合併忙碌時段。
- 天際線問題：掃描線配合堆積追蹤目前最高的建築。
- 計算幾何：線段相交、矩形聯集面積，都是掃描線的經典應用。
取捨與陷阱
- 端點相同時的順序決定答案：區間是 [s, e) 就要先處理結束，否則 10 點結束和 10 點開始的兩場會議會被算成重疊。
- 合併行事曆時，緊接的區間（[1, 3) 和 [3, 5)）通常要合成一段，和「有沒有重疊」是不同的問題。