题目描述

C++模板题：区间合并

C++代码

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
vector<PII> alls;
int n, l, r;

void merge(vector<PII> &segs){ //这个模板真是八达鸟
    vector<PII> res;
    int st = -1e9, ed = -1e9;
    sort(segs.begin(), segs.end()); //pair排序优先以左端点排，再以右端点排
    for(auto item : segs){
        if(ed < item.first){ //没交集
            if(st != -1e9) //将之前搞好的区间放进去
                res.push_back({st, ed});
            st = item.first; 
            ed = item.second;
        }
        else //新来的区间有交集 
            ed = max(ed, item.second);
    }
    if(st != -1e9) //这个最终得到的区间进去
        res.push_back({st, ed});
    segs = res;
}

int main(){
    cin >> n;
    while(n--){
        cin >> l >> r;
        alls.push_back({l, r});
    }
    merge(alls);
    //for(auto item : alls)
    //    cout << item.first << "---" << item.second << endl;
    cout << alls.size() << endl;
}