题目描述

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。输出合并完成后的区间个数。

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

输入格式

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

输出格式

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

1≤n≤1000001≤n≤100000,
−109≤li≤ri≤109

样例

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

算法1

贪心：先将区间按照左端点排序；当当前区间于后面区间没有交点时加入结果区间集，否则合并区间；

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;

void merge(vector<PII>&segs)
{
    vector<PII>res;//结果
    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.first);
    }
    if(st!=-2e9)
        res.push_back({st,ed});
    segs=res;

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

    }
    sort(segs.begin(),segs.end());//pair先按第一个元素排序，再按第二个元素排序
    merge(segs);
    cout<<segs.size();
    return 0;
}