区间合并

区间合并

两个区间若是有交集，则可以合并成一个区间。

输入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){
    // 先按照左端点排序 由于是pair 左端点排序右端点也会跟着排
    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;
    }
    // 最后一组区间一定要手动加入
    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;
}