區(qū)間合并

兩個(gè)區(qū)間若是有交集，則可以合并成一個(gè)區(qū)間。

輸入n個(gè)區(qū)間，把所有有交集的區(qū)間合并。

算法步驟：

• 按照區(qū)間左端點(diǎn)排序
• 然后固定一個(gè)區(qū)間和后面區(qū)間進(jìn)行比較

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
int n;
vector<PII> segs;
vector<PII> res;
void merge(vector<PII> &segs){
    // 先按照左端點(diǎn)排序 由于是pair 左端點(diǎn)排序右端點(diǎn)也會(huì)跟著排
    sort(segs.begin(),segs.end());
    int st = -2e9,ed = -2e9;
    for(auto seg:segs){
        if(ed < seg.first){
            if(st != -2e9){
                res.push_back({st,ed});
            }
            st = seg.first,ed = seg.second;
        }else{
            ed = max(ed,seg.second);
        }
        //cout << res.size() <<endl;
    }
    // 最后一組區(qū)間一定要手動(dòng)加入
    if(st != -2e9) res.push_back({st,ed});
}


int main(){
    cin >> n;
    for(int i = 0; i<n;i++){
        int l,r;
        cin >> l >> r;
        segs.push_back({l,r});
    }   
    merge(segs);
    cout << res.size() << endl;
    return 0;
}