掃描線

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

你會學到三件事

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

開始之前

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

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

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

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

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

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

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

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

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

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

於是每個人變成兩個 pair：

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

三、排序，然後掃一遍

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

按時間排好，從左掃到右，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，所以預設是先離場。

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

完成的樣子

int main() {
    vector<pair<int, int>> events;
    events.push_back(make_pair(1, 1));
    events.push_back(make_pair(5, -1));
    sort(events.begin(), events.end());
    int cur = 0, best = 0;
    for (int i = 0; i < 2; i++) {
        cur = cur + events[i].second;
        if (cur > best) best = cur;
    }
    cout << best << endl;
    return 0;
}

換你了

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

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

這一課你做了什麼

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

如果卡住了