[区间问题] 区间选点(区间问题+贪心)

0. 前言

玄学的贪心问题，一般全凭直觉。

贪心问题没有固定讨论，没有模板，见多了就好了，证明想法的正确性是很困难的，大多采用反证法。

1. 区间问题+贪心

905. 区间选点

贪心思路：

• 区间按右端点从小到大排序
• 从前往后依次枚举每个区间
  • 如果当前区间中已经包含点，则直接跳过该区间
  • 否则，选择当前区间的右端点

证明：

• 假设最优解为 ans 个，以上述贪心思路选出来的点为 cnt 个。即证明 ans = cnt，等价于 ans >= cnt && ans <= cnt
• 首先，以上述贪心思路选择出的 cnt 个点，是一组可行方案。其覆盖了所有区间，满足题目要求。且 ans 是最优解，即为可行方案的最小值，那么 ans <= cnt 成立
• 其次，注意这 cnt 个点是如何被选出来的。因为区间按照右端点排序后，每一个 cnt 都是没有被覆盖的区间右端点，则说明这 cnt 个区间是两两不交的，则至少需要 cnt 个点才能将这些两两不交的区间进行覆盖，故 ans >= cnt 成立

时间复杂度：$O(nlogn)$

代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+5;

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

int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        range[i] = {a, b};
    }
    
    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;
    
    cout << res << endl;
    
    return 0;
}