# b966. 第 3 題 線段覆蓋長度
##### link: https://zerojudge.tw/ShowProblem?problemid=b966
###### tags: `APCS`
#### 先將輸入的pair排序，之後利用 queue 紀錄現在的區段，執行以下判斷：
1. *第25行* : 如果 queue 中現在的區間範圍完全包含 table[i] 中的區段，則繼續
2. *第26行* : 如果進來的是和現在區段完全沒有交集的區段，將 queue 中的區段改成此區段，並加上該線段長度。
3. *第31行* : 如果進來的區段完全包含現在的區段，將 queue 中的區段改成此區段，並加上多出部分的長度
4. *第36行* : 如果進來的區段左邊超出現有區段，而右邊沒有，則將它的右界修改成 cur.second
5. *第41行* : 和第四點類似

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios:: sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    int ans=0;
    cin>>n;
    pair<int,int> cur;
    vector<pair<int,int>> table(n);
    for (int i=0;i<n;i++){
        cin>>table[i].first>>table[i].second;
    }
    sort(table.begin(),table.end());
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++){
        if (q.empty()){
            q.push(table[i]);
            ans+=abs(table[i].second-table[i].first);
        }
        else {
            cur=q.front();
            if (table[i].first>=cur.first && table[i].second<=cur.second) continue; //包含
            else if ((table[i].second <= cur.first) || (table[i].first >= cur.second)){ // 毫不相干
                q.pop();
                q.push(table[i]);
                ans+=abs(table[i].second-table[i].first);
            }
            else if(table[i].first < cur.first && table[i].second > cur.second){
                ans+= abs(cur.first-table[i].first) + abs(cur.second - table[i].second);
                q.pop();
                q.push(table[i]);
            }
            else if (table[i].first < cur.first && table[i].second <= cur.second){
                ans+=abs(cur.first-table[i].first);
                table[i].second = cur.second;
                q.pop(); q.push(table[i]);
            }
            else if (table[i].first >= cur.first && table[i].second > cur.second){
                ans+= abs(cur.second-table[i].second);
                table[i].first =cur.first;
                q.pop(); q.push(table[i]);
            }
        }
    }
    cout<<ans;

    return 0;
}