掃描線

把「區間」變成「兩個事件」。 · ⏱ 約 35 分鐘

你會學到三件事

1. pair 把兩個值綁在一起
2. 一段區間可以拆成「開始 +1」和「結束 −1」
3. 排完序掃一遍，O(n log n) 解掉一個 O(n²) 的題

開始之前

題目：n 個人各有進場和離場時間，問同時在場的最多幾人。

直覺做法是「每個時刻數一次」，而時間範圍大的話那是 O(範圍 × n)，太慢。

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、pair：把兩個值綁在一起

pair 把兩個值當成一個東西：

1pair<int, int> p = make_pair(1, 2);2cout << p.first << " " << p.second << endl;

⚠️ pair 排序時先比 first，一樣才比 second。

這件事是這一課的關鍵：sort 一個 vector<pair<...>> 不用寫比較函式。

（也可以寫 {1, 2} 代替 make_pair(1, 2)，兩個都通。）

積木盤上這一顆寫著「建立配對 … …」， 而 p.first 那種取法是「結構 … 的欄位 …」。

二、🔴 一段區間 = 兩個事件

一個人從 a 待到 b。不要想成「一段」，想成兩件事：

時刻 a：人數 +1
時刻 b：人數 −1

於是每個人變成兩個 pair：

1events.push_back(make_pair(a, 1));      // 進場2events.push_back(make_pair(b, -1));     // 離場

三、排序，然後掃一遍

照著打上這一段，排完之後只走一遍：

1sort(events.begin(), events.end());2int cur = 0, best = 0;3for (int i = 0; i < events.size(); i++) {4    cur = cur + events[i].second;5    if (cur > best) best = cur;6}

按時間排好，從左掃到右，cur 就是「現在有幾人」。

時刻:   1    3    5    7
事件:  +1   +1   -1   -1
cur:    1    2    1    0
                 ▲
              最大是 2

O(n log n)（排序）＋ O(n)（掃一遍），而原本是 O(範圍 × n)。

掃描線的核心不是那個迴圈，是「把區間拆成端點」那一步。 一段連續的東西變成兩個離散的事件，於是它可以被排序。

四、⚠️ 同一時刻的順序

如果一個人 5 點離場、另一個 5 點進場，先算哪個？

• 「同時在場」不算相碰 → 先 −1（把 -1 排在前面）
• 算相碰 → 先 +1

pair 排序先比 first（時間）、再比 second。 而 -1 < 1，所以預設是先離場。

⚠️ 題目要哪一種要看清楚，這種差一格的錯很難從答案看出來。

完成的樣子

1#include <algorithm>2#include <iostream>3#include <utility>4#include <vector>5using namespace std;6int main() {7    vector<pair<int, int>> events;8    events.push_back(make_pair(1, 1));9    events.push_back(make_pair(5, -1));10    sort(events.begin(), events.end());11    int cur = 0, best = 0;12    for (int i = 0; i < 2; i++) {13        cur = cur + events[i].second;14        if (cur > best) best = cur;15    }16    cout << best << endl;17    return 0;18}

換你了

加幾個人進去（例如 (2,4)、(3,6)），確認答案是對的。

再想一個：同樣的手法怎麼算「總共被覆蓋的長度」？ 提示：記住上一個事件的時間，cur > 0 的時候累加時間差。

到編輯器做這一題：練習：加幾個人進去，確認答案是對的

做一個

三場會議：1~5、2~6、3~4。印出最多有幾場同時在進行。

🔴 把每一場拆成「開始 +1」和「結束 −1」兩個事件，排序，掃一遍。 ⚠️ 而兩兩比較的做法是 O(n²)，這一題資料小看不出來，n 上萬就跑不完了。

到編輯器做這一題：做一個：最多幾場會議同時在開

這一課你做了什麼

• 你用 pair 綁了時間和變化量
• 你把每段區間拆成了兩個事件
• 你排序後掃一遍，解掉了一個原本很慢的題目

如果卡住了