# Zerojudge b966: APCS第三題 線段覆蓋長度
> **Link:** [Zerojudge b966](https://zerojudge.tw/ShowProblem?problemid=b966)
---
## Description:

給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一次。

例如給定 4 個線段：$(5, 6)、(1, 2)、(4, 8)、(7, 9)$，如下圖，線段覆蓋長度為 6 。


---
## Input Format & Output Format

| Input Format | Output Format |
|:--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------:|:------------------------------------------------------------:|
| 第一列是一個正整數 $N$ ，表示此測資有 $N$ 個線段。接著的 $N$ 列每一列是一個線段的開始端點座標整數值 $L$ 和結束端點座標整數值 $R$ ，開始端點座標值小於等於結束端點座標值，兩者之間以一個空格區隔。其中30%的測資滿足， $N < 100 ， 0 ≤ L , R < 1000$ ，並且線段沒有重疊。其中70%的測資滿足， $N < 100 ， 0 ≤ L , R < 1000$ ，並且線段可能重疊。其中100%的測資滿足， $N < 10000 ， 0 ≤ L , R < 10000000$ ，並且線段可能重疊。 | 輸出其總覆蓋的長度。本題為嚴格比對，請務必按照說明進行輸出。 |
| | |

---

## Sample Input & Output

**Input:**
輸入範例一：
5
160 180
150 200
280 300
300 330
190 210

輸入範例二：
1
120 120

**Output:**
輸出範例一：
110

輸出範例二：
0

---
## 解題歷程

**【解題想法】**:排序
**【Tag】**:排序(Sorting)、貪心(Greedy)、掃描線(Sweep Line)
* {x, y}：每個線段的「起點」座標 x 和「終點」座標 y。
* 排序：x 由小到大排序，x 相同的話，y 由大到小排序。
* 變數 left：目前線段的「起點」座標。
* 變數 right：目前線段的「終點」座標。

作法1-Sweep Line :

#include <bits/stdc++.h>
using namespace std;
#define AC ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int> 
#define f first
#define s second
bool cmp(pii a,pii b) {
    if(a.f==b.f) return a.s>b.s;
    else return a.f<b.f;
}
int main() {
    AC
    int n,x,y;
    while(cin>>n) {
        vector<pii> v;
        for(int i=0;i<n;i++) {
            cin>>x>>y;
            v.push_back({x,y});
        }
        sort(v.begin(),v.end(),cmp);
        int left=0,right=0,ans=0;
        for(int i=0;i<v.size();i++) {
            if(v[i].f>=left) {
                ans+=(right-left);
                left=v[i].f;
                right=v[i].s;
            }else if(v[i].s>left){
                right=v[i].s;
            }
        }
        ans+=(right-left);
        cout<<ans<<'\n';
    }
    return 0;
}

作法2-把線段的開始端點和結束端點視為獨立的evnet，記錄覆蓋的線段數 :

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main() {
    int N, L, R;
    cin >> N;
    vector<pair<int,int>> v;
    for (int i = 0; i < N; i++) {
        cin >> L >> R;
        //把線段的開始端點和結束端點視為獨立的evnet
        //在線段的開始端點L處，event +1
        v.push_back({L, 1});
        //在線段的結束端點R處，event -1
        v.push_back({R, -1});
    }
    sort(v.begin(), v.end());
    //now指向目前檢視的event
    //event為該座標點i, 對應一個左閉由開區間[i, i+1), 共被幾段線段覆蓋
    int now = 0, event = 0, ans = 0;
    for (int i = 0; i <= 1e7; i++) {
        while (now < (int)v.size() && v[now].first == i) {
            event += v[now].second;
            now++;
        }
        if (event > 0) {
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}