# 前言

掃描線就如他的名字一樣，通常是由一個方向掃到另一個方向，然後就只需要判斷新掃到的地方來做判斷，通常會搭配排序。

# 這一章篇幅不長，因為掃描線本身更像是一種觀察問題的角度，而不是一套獨立的演算法 —— 它常常是貪心（1-5）或雙指針（1-3）的具體實現方式。理解它的關鍵在於抓住「掃描線」這個比喻本身。

# 什麼是掃描線

想像一條線（可以是時間軸、數線、或平面上的一條垂直線）從左掃到右。掃描過程中，我們只需要維護「目前掃到的位置」相關的資訊，不需要每次都重新檢視所有資料 —— 這正是它能把複雜度降下來的原因。

掃描線通常搭配三個步驟：

1. 把所有「事件」按座標排序（例如區間的起點、終點）
2. 依序處理每個事件，掃描線移動到該事件的位置
3. 維護一個資料結構，回答「掃描線目前位置」相關的查詢

這個套路能生效，前提跟雙指針一樣是單調性：一旦掃描線往右移動，就不會再回頭，所以每個事件只會被處理一次，整體複雜度通常是 O(n log n) （排序）加上 O(n) （掃描）。

# 例題：監看華山練功場（AP325）

華山派有 n 個弟子，每個弟子的練功時間都不盡相同，第 i 個弟子到練功場所練功的時間是區間 [s (i),t (i))。最近華山頗不平靜，掌門岳不群要求令狐沖找一些弟子練功時順便監看練功場，對於想要監看的時間區間 [x,y)，請問他最少只要找幾位弟子，這些弟子的練功時間就可以涵蓋整個 [x,y)。

輸入說明：第一行是個正整數 n，第二行是兩個整數 x 與 y，接著的 n 行每一行有兩個整數 s (i) 與 t (i)，同行相鄰兩數之間空白區隔。n 不超過 1e5，0≤x<y≤1e9，且對所有 i，0≤s (i)<t (i)≤1e9。

輸出說明：練功時間可以涵蓋 [x,y) 的最少的弟子數。如果無解輸出 -1。

這一題其實也不用想的太難找 y 最大那邊不用什麼技巧傻傻的掃過去一遍就好了，掃描線的題目大概就是這種感覺。

# 解題思路

這是 ** 區間覆蓋（interval covering）** 的經典模型，貪心規則是：從目前已覆蓋到的位置 x 開始，在所有起點 ≤ x 的候選裡，挑選結尾最遠的那個。這正是貪心（見 1-5）跟掃描線的結合 —— 掃描線負責「依序看到哪些候選變得可用」，貪心負責「在可用的候選裡挑最好的」。

// [自己的解法]

#include <bits/stdc++.h>

using namespace std;

#define N 100005

bool cmp(pair<int,int> a,pair<int,int> b){

    if(a.first != b.first){

        return a.first < b.first;

    }else{

        return a.second <= b.second;

    }

}

int n,x,y;

pair<int,int> p[N];

int main(){

    cin>>n;

    cin>>x>>y;

    for(int i=0;i<n;i++)

        cin>>p[i].first>>p[i].second;

    sort(p,p+n,cmp);// 由小到大排序

    int i=0,ans=0;

    while(x<y){

        int temp=i;

        while(i<n && p[i].first <= x){

            // 從監看起點小於等於 x 的人中挑選 y 最大的人

            if(p[temp].second > p[i].second) temp=i;

            i++;

        }

        //p [temp].first > x 這行是為了排除 x 到 y 的區間中間有沒被包在範圍的狀況

        // 後方的則是判斷已經沒有人可以選了可還是有區間沒被包道

        if(p[temp].first > x || (i>=n && p[temp].second < x)) {

            cout<<"-1";

            return 0;

        }

        ans++;

        x=p[temp].second;

    }

    cout<<ans;

}

這裡的「掃描線」體現在 while(i<n && p[i].first <= x) 這一段： i 只會往前移動，永遠不會回頭，每個候選人只會被檢查一次，這就是掃描線省時間的地方。搭配貪心規則「挑結尾最遠的那個」，整體複雜度是排序的 O(n log n) 加上一次線性掃描 O(n) 。

# 掃描線的常見應用場景

雖然這章只有一個主要例題，但掃描線的思路在很多地方都會用到，這裡列出幾個常見場景，幫助之後辨認：

• 區間覆蓋 / 區間排程：如本章例題，或 1-5 提過的活動選擇問題
• 求多個區間的聯集長度：把所有起點標記 +1、終點標記 -1，排序後掃過去，用一個計數器判斷目前是否被覆蓋
• 平面幾何問題：例如求矩形聯集面積、最近點對問題，讓一條垂直線橫掃整個平面，搭配一個資料結構（如 set、線段樹）動態維護掃描線上的資訊
• 時間序列的事件處理：把「進入」和「離開」都當成事件，按時間排序後依序處理

# 判斷可不可以用掃描線

如果問題可以被描述成「一連串按座標排序的事件」，而且處理每個事件只需要知道當下的狀態（不需要回頭看已經處理過的事件的細節），那就很適合用掃描線。反過來說，如果每個事件的處理都需要跟所有其他事件比較，那掃描線可能就幫不上忙，要考慮別的資料結構。

# 小結

掃描線的核心心法只有一句話：排序後往一個方向掃，只維護當下需要的資訊。它本身不是一個獨立於貪心、雙指針之外的新技巧，而是這些技巧在處理「一維座標上的事件」時的具體展現。

下一章要講分治演算法 —— 把問題切成兩半分別解決，再合併答案。跟掃描線「一路往前不回頭」的線性思路不同，分治是「遞迴地一分為二」的樹狀思路。

# 練習題

（之後補上）