区间合并

对于任何一个区间segs，我们需要将他们合并得到一个新的区间数组。比如[1, 2]，[2, 3]，[5, 7]，[6, 9]，就可以合并成[1, 3]，[5, 9]，合并成了两个区间。

方法其实不难，首先我们存储segs数组。然后我们将segs对x从小到大排序，这样就保证了局部有序，合并区间就不会出现缺少的情况。

接下来就是合并操作，先定义临时的区间端点st和ed。然后遍历区间数组。如果当前数组的值的x大于临时数组中的ed，那么就说明当前区间st和ed是无法继续合并的（已经最大了），所以加入到结果中。否则的话，就要更新最大的ed。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
int n;
vector<PII> segs;

void merge(vector<PII> &segs) {
    vector<PII> res;
    //  先对x从小到大排序
    sort(segs.begin(), segs.end());
    //  初始化区间的左右端点均为-inf
    int st = -2e9, ed = -2e9;
    //  遍历排序好的区间
    for(auto seg : segs) {
        //  如果当前区间的右端点比下一个区间的左端点小的话，说明当前区间已经无法继续合并，加入到结果
        if(ed < seg.first) {
            //  这个if判断是防止误加入。
            if(st != -2e9) res.emplace_back(st, ed);
            //  加入后，更新当前最新的端点
            st = seg.first, ed = seg.second;
        }else ed = max(ed, seg.second);     //否则就更新右端点
    }
    //  因为当前循环有最后的结果没有加入，所以这里是一个补充，防止少一个区间
    if(st != -2e9) res.emplace_back(st, ed);
    segs = std::move(res);
}

int main() {
    int n;
    cin >> n;
    while(n--) {
        int x, y;
        cin >> x >> y;
        segs.emplace_back(x, y);
    }
    //  区间合并模版
    merge(segs);
    cout << segs.size();
    
    return 0;
}