区间合并

算法思路

对于一个二元组，我们可以用pair，也可以自己构造结构体
用pair的优点是，里面的构造、析构、比较一些函数是已经写好的，以后直接调用就行

区间合并有一些贪心的思想

首先我们要按区间左端点排序，每当下一个区间的左端点小于等于当前区间的右端点，那么就是可以合并的。右端点更新。如果大于的话，那么之前的区间是不能再进行合并的了，将之前的区间放入答案里面

如果需要证明正确性，可以采用反证法，或者数学归纳
1. 反证法，假设我们对$n$个区间进行该操作后的到的不是答案，那么必然存在两个区间有交集。
但是按照上述流程，最后留不下来交集。与假设矛盾，该算法成立
2. 数学归纳法，假设前$n$个区间已经合并完(合并后的区间，两两之间均无交集)，在加入第$n + 1$区间时，若存在交集，则是与之前合并的最后一个区间右端点有交集，否则无交集，不需合并。所以按上述算法可以得到正确解。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;//st当前区间左端点，ed当前区间右端点
    for (auto seg : segs)//C++11里基于范围的遍历
        if (ed < seg.first)//当前区间右端点小于下一个区间左端点，也就是说无法合并了
        {
            if (st != -2e9) res.push_back({st, ed});//如果当前区间不为空，就在答案里加入当前区间
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);//否则更新当前区间右端点

    if (st != -2e9) res.push_back({st, ed});//扫尾
    //最后，如果当前区间内不为空，那么将当前区间加入进答案
    segs = res;
}

int main()
{
    int n;
    scanf("%d", &n);

    vector<PII> segs;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;
}