鄙人才疏学浅，此中鄙陋甚多，望海涵！

题目描述

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

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

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

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

输入格式
第一行包含整数n。

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

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

数据范围
1≤n≤100000,
−109≤li≤ri≤109

样例

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

算法1

vector<int> 容器遍历法（时间复杂度较高）

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
vector<PII> segs;
void merge(vector<PII>&segs)
{
    vector<PII> res;
    sort(segs.begin(),segs.end());
    int l=-2e9,r=-2e9;
    for(auto item:segs)
    {
        if(r<item.first)
        {
            if(l!=-2e9) res.push_back({l,r});
            l=item.first;
            r=item.second;
        }
        else r=max(r,item.second);
    }
    if(l!=-2e9) res.push_back({l,r});
    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()<<endl;
    return 0;
}

算法2

贪心结构体优化（用时约为上一种算法的三分之一）

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e5+10;

struct Range
{
    int l,r;
    bool operator<(const Range &W)const
    {
        return l<W.l;
    }
}range[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        range[i]={l,r};
    }
    sort(range,range+n);
    int res=0,st=-2e9;
    for(int i=0;i<n;i++)
    {
        if(st<range[i].l)
        {
            res++;
            st=range[i].r;
        }
        else st=max(range[i].r,st);
    }
    cout<< res <<endl;
    return 0;
}

其中贪心按右端点排序的操作也按左端点排序的操作算是镜像操作，倒着往回比就可以！

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=1e5+10;

struct R
{
    int l,r;
    bool operator<(const R &W)const
    {
        return r<W.r;
    }
}ranges[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        ranges[i]={l,r};
    }
    sort(ranges,ranges+n);
    int cnt=1,st=ranges[n-1].l;
    for(int i=n-2;i;i--)
    {
        if(st<=ranges[i].r) st=min(st,ranges[i].l);
        else
        {
            st=ranges[i].l;
            cnt++;
        }
    }
    cout<< cnt <<endl;
    return 0;
}