区间选点：贪心——acwing

题目：

905. 区间选点 - AcWing题库

分析

排序右端点，右端点是固定在上一个区间外边的，右端点排序之后，下一个右端点只能在上一个区间外边。

此时，弹性没那么强，左端点做伸缩判断，也就是很容易看出区间是否相交。

而排序左端点，左端点可以在区间内部，右端点也是可以在区间内部，此时弹性太强。不好判断。

因此排序右端点。

代码 

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

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 l, r;
        cin >> l >> r;
        range[i] = {l,r};
    }
    // sort右端点 // range里边有重载函数定义
    sort(range, range + n);
    // 选点每次选 右端点，因为按右端点排序，可以可以尽可能覆盖多个区间，
    // 选右端点就是局部最优的体现
    int res = 0, end = -2e9;
    // 枚举区间 一一判断选点（已覆盖直接pass，没覆盖则更新，选局部最优解点）
    for(int i = 0; i < n; i ++) {
        //当前左区间 选点值
        if(range[i].l > end) {
            res ++; // 选点＋1
            end = range[i].r; //更新为当前右区间
        }
    }
    cout << res << endl;
    return 0;
}

原文地址：https://blog.csdn.net/2401_87338545/article/details/144024348

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！