区间选点

贪心问题概述

贪心算法，是用计算机来模拟一个“贪心”的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响，也就是每次都选取局部最优解

但局部最优解不一定是全局最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解

区间贪心概述

一般是对左端点或者右端点进行排序，排序后取找到一个符合题意的方法，然后试几个例子，都对了，就试着简单证明下，能说服自己就去写

常用的证明思路

贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明

反证法：
如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。

归纳法：
先算得出边界情况$($例如$n$ $=$ $1)$的最优解$F(1)$，然后再证明：对于每个$n$，$F(n + 1)$都可以由$F(n)$推导出结果

思路分析

$(1)$ 将区间按右端点升序排列

$(2)$ 初始化选点为负无穷，每次看当前区间左端点和它的大小关系
1. 左端点大于选点，说明选点和当前区间无交集，那么我们选点数量加一，选点赋值为当前区间的右端点
2. 左端点小于等于选点，说明选点在当前区间上，那么就看选点和下一个区间的关系

证明

上面是一个很直观的思路，因为我们如果从左向右遍历区间时候，选点在一个区间的右端点时候比其它点好，因为右端点相对于该区间上的其他点，总是更可能的覆盖下一个区间。如果右端点都覆盖不上，那么其他点是更不可能覆盖上去减少选点

下面将给出证明，在这里常用证明的方法是反证法，以及 $a$ $>=$ $b$与$b$ $>=$ $a$推出$a$ $==$ $b$

我们将答案选点个数记为$ans$，按此算法得出的选点个数记为$cnt$

证明 $cnt$ $>=$ $ans$

我们这种选法是覆盖了所有区间，它是一种合法方案，所以大于等于最少选点

证明 $ans$ $>=$ $cnt$

我们选的点都是区间的右端点，也就是说我们也选出来$cnt$个区间，按步骤可以知道，这$cnt$个区间互补重叠。这时覆盖这$cnt$个区间最少的就是$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;
}