最大不相交区间数量

思路分析

$(1)$ 将区间按右端点升序排列
$(2)$ 从左向右遍历区间，初始化选点为负无穷
1. 选点大等于于当前区间的左端点，区间存在冲突，不选
2. 选点小于当前区间左端点，区间不冲突，更新选点为当前区间右端点，区间数量递增

证明

这个思路也是非常好想的。对于每一个区间，如果想让他与上一个区间不冲突，那么上一个区间的右端点越小越有利，越不容易冲突。所以我们选的时候也优选右端点小的

详细证明如下，答案区间数量为$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 ++ ) scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n); // 排序

    int res = 0, ed = -2e9; // ed表示上一个区间的右端点
    for (int i = 0; i < n; i ++ )
        if (range[i].l > ed) // 如果不冲突
        {
            res ++ ; // 区间数量增加
            ed = range[i].r; // 更新上一个区间右端点
        }

    printf("%d\n", res);

    return 0;
}