题目内容

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

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

输入格式

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

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

输出格式

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

数据范围

1≤N≤10^5 ,
−10^9≤$a_i$≤$b_i$≤10^9

输入样例

3
-1 1
2 4
3 5

输出样例

2

题解

与上题一样的思路。
思路如下：
1、将每个区间按右端点从小到大排序
2、从前往后依次枚举每个区间。
如果当前区间已经被覆盖，则直接pass。否则选择当前区间的右端点。

简单证明
首先，我们选择的cnt是可行的方案数，ans是所有可行方案的最大值，因此ans≥cnt。
然后，按照选择思路，会选出cnt个点，所有的区间每一个区间至少包含一个我们选择的点，因此通过反证法，假设ans大于cnt，就意味着可以选择出比cnt更多相互之间没有交集的区间，也就需要ans个点，又因为cnt满足了每个区间至少包含一个选择的点，所以ans＞cnt不成立，因此只能是ans=cnt。

代码

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;

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

int main(){
    scanf("%d",&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, ed = -2e9;
    
    for(int i = 0;i<n;i++){
        if(ed < range[i].l){
            res++;
            ed = range[i].r;
        }
    }
    printf("%d\n",res);
    return 0;
}