博客

题目分析：

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

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

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

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

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含两个整数 ll 和 rr。

输出格式

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

数据范围

1≤n≤1000001≤n≤100000,

−109≤li≤ri≤109−109≤li≤ri≤109

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

核心算法 区间合并的思想

将有交集的区间进行合并

1.按区间左端点排序

2.分情况讨论合并过程中区间的三种关系

思考过程 如果要将区间合并

假定第i个区间 则下一个区间和他的位置关系有三种

1.包含于i

2.左端点在i区间里面

3.左端点在i区间外面

根据算法可划分为两种情况

1.可以合并

2.不能合并

题解如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5+10;
int n;
vector<PII> segs;

void merge(vector<PII> &segs){
    vector<PII> res;
    //按照左端点对segs进行排序
    sort(segs.begin(),segs.end());
    //刚开始定义区间左右端点都是负无穷 保证遍历的第一个区间可以被后续执行
    int st=-2e9,ed=-2e9;
    for(auto seg:segs){
        //这是两个区间不能合并的情况 只有当两个区间没有交集时 才会进行下列操作
        if(ed<seg.first) {
            //如果区间没有交集 并且此区间不为空 则将维护的区间压入res
            if(st!=-2e9) res.push_back({st,ed});
            //已经将前面的区间压入 将维护区间改为下一个区间
            st = seg.first,ed = seg.second;
        }
        //区间有交集的情况
        else {
            //此时需要将维护的区间的右端点改为区间并集的最大值
            //注意 此时不能直接将并集压入res 因为并集可能与后面的区间还有交集 
            ed = max(ed,seg.second);
        }
    }
    //保证区间不为空时 将最后一个区间压入res
    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()<<endl;
    return 0;

}