题解

这道题的做法：

• 首先将录入的按照区间的左值排序；
• 弄清楚排序后的数组中，前一个区间与后一个区间可能的关系
• 主要为下面三种：
  

弄清楚之后就可以理解y总的模板；

• 模板：

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

    sort(segs.begin(),segs.end());      //要将其先sort

    int st = -2e9,ed = -2e9;

    for(auto seg:segs)
    {
        if(ed < seg.first)  //如果第二个区间完全不在维护区间内
        {
            if(st != -2e9) res.push_back({st,ed});   //这里要判断st是否为我们给的最左值，如果是则不插入到答案
            st = seg.first,ed = seg.second;
        }else ed = max(ed,seg.second);      //如果是其他两种情况，那么更新区间右值
    }

    if(st != -2e9) res.push_back({st,ed});      //将最后一个区间插入到答案中，

    segs = res;
}

C++ 代码

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

using namespace std;

typedef pair<int,int> PII;

vector<PII> segs;

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

    sort(segs.begin(),segs.end());      //要将其先sort

    int st = -2e9,ed = -2e9;

    for(auto seg:segs)
    {
        if(ed < seg.first)  //如果第二个区间完全不在维护区间内
        {
            if(st != -2e9) res.push_back({st,ed});   //这里要判断st是否为我们给的最左值，如果是则不插入到答案
            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;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin >> l >> r;
        segs.push_back({l,r});
    }

    merge(segs);

    cout << segs.size();
    return 0;
}

反思

• st,ed初值设置为-2e9的目的是为了判空；
• 如果题目规定了没有空数据，那么可以直接将数组的第一个区间赋给st，ed；