区间合并

区间合并

描述：

​ 合并所有有交集的区间。

思路：

​ 可以用vector<pair<int, int>> 进行存储所有的区间

（1）先将所有的区间进行从小到大排序
（2）然后用所有的小区间去维护一个大区间
（2.1）依次去遍历每一个小区间
（2.2）如果当前区间和上一个区间没有交集，则进将前一个区间放入答案中，然后开始维护当前区间
（2.3）如果当前区间和上一个区间有交集，就更新右边界为较大的那个值
（3）最后特判一个，如果最后一个区间不为空，就将最后一个区间放入到答案中
（4）将答案赋值给原集合即可

代码模板：

for (int i = 0; i < n; i ++)
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r}); 
    }

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

    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);   //将区间右边界更新为较大的那个值
        }
    }

    if (st != -2e9) res.push_back({st, ed});    //将最后一个区间加入

    segs = res;
}

注意：

​ （1）需要先对原区间集合进行排序

​ （2）需要特判没有交集的是不是第一个区间，是不是最开始维护的空区间

​ （3）在将区间集合遍历结束后，需要判断，只要维护的区间被更新过，那么加一定存在一个区间还没有加入答案，因为它还没有遇到一个与他没有交集的区间。