最大不相交区间数量

给定 N 个闭区间 [ai,bi],请你在数轴上选择若干区间,使得选中的区间之间互不相交(包括端点)。

输出可选取区间的最大数量。

输入格式

第一行包含整数 N,表示区间数。

接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。

输出格式

输出一个整数,表示可选取区间的最大数量。

数据范围

1≤N≤1e5
−1e9≤ai≤bi≤1e9

输入样例:

3
-1 1
2 4
3 5

输出样例:

2

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
struct Node
{
    int l;
    int r;
}a[N];
bool cmp(Node a,Node b)
{
    return a.r<b.r;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int l,r;
        cin>>l>>r;
        a[i].l=l,a[i].r=r;
    }
    sort(a+1,a+n+1,cmp);
    int end=-2e9,res=0;
    for(int i=1;i<=n;++i)
    {
        if(a[i].l>end)
        {
            res++;
            end=a[i].r;
        }
    }
    cout<<res<<endl;
    system("pause");
    return 0;
}