【题解】区间合并

区间合并代码模板

void merge(vector<PII> &segs)
{
    vector<PII> res;
    
    sort(segs.begin(),segs.end());
    int st=-2e9,ed=-2e9;
    
    for(auto seg:segs)
    {
        if(seg.first > ed)
        {
            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;
}

区间合并思想：

• 维护一个区间，如果无法继续维护，就更新为新的区间

区间合并图示：

区间合并细节

• 通常我们用pair来存每个区间
• 首先对vector进行排序，sort默认对pair第一个元素进行排序
• 然后进行区间合并，需要注意我们开始维护的区间要设为极小值

用法：

题目链接：区间合并

题意：

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

1≤n≤100000
−10⁹ ≤ li ≤ ri ≤ 10⁹

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

代码

#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;
    
    sort(segs.begin(),segs.end());//一定要排序，sort对pair排序时默认先对first排序
    int st=-2e9,ed=-2e9;//开始时一定要将左右区间设为极小值
    
    for(auto seg:segs)
    {
        //如果新的区间严格大于我们所维护区间，更新所维护区间
        if(seg.first > ed)
        {//如果一个区间已经维护完毕，将其加入到seg，//特判第一个区间，注意是st是否为-2e9，
            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()
{
    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;
}