贪心-区间问题——acwing

题目一：最大不相交区间数量

908. 最大不相交区间数量 - AcWing题库

分析

跟区间选点一样。区间选点：贪心——acwing-CSDN博客

代码

#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;
}

题目二：区间分组

906. 区间分组 - AcWing题库

分析

首先用一个二维数组将 区间左右端点存起来。这是数据的存储结构

对左端点排序。

贪心：

每次取所有集合中最小的右端点 与 当前区间左端点比较，如果左端点小于说明可以放入结合，也就是更新该集合的右端点。否则，多一个集合，直接入堆。

用小根堆来维护所有集合，因为贪心每次取最小，所以用小根堆维护所有结合的最右端点。

其实就是两个思考，

1. 一是如何存储区间
2. 二是如何解决问题

核心问题通过贪心来解决，按左端点排序

因为涉及最值，用小根堆来存储集合，维护集合。每个集合只需要存储每个集合的有端点。每次都用最小的来比较，这样可以更区间分组更密集，同时如果最小的都不行，那更大的也不行，会有交集，就需要另开集合。

代码

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

vector<vector<int>> a(100010,vector<int> (2,0)); 
int n;

int main() {
    cin >> n;
    for(int i = 0; i < n; i ++) {
        int l, r;
        cin >> l >> r;
        a[i][0] = l, a[i][1] = r;
    }
    sort(a.begin(),a.begin()+n); // 最左端点排序
    // 小根堆，存所有集合的右端点，集合大小就是
    priority_queue<int,vector<int>,greater<int>> s;
    //遍历区间
    for(int i = 0; i < n; i ++) {
        //集合中 最小 右端点 都比 左端点； 入队多一个集合
        if(s.empty() || s.top() >= a[i][0]) s.push(a[i][1]);
        else { // 当前左端点大，更新最小右端点
            s.pop();
            s.push(a[i][1]);
        }
    }
    // 因为用小根堆，存储每一个集合的最后区间右端点，故右端点个数也是集合个数也是组数。
    cout << s.size() << endl;
    return 0;
}

题目三：区间覆盖

907. 区间覆盖 - AcWing题库

分析

考虑，区间存储结构，排序左端点，可以使用二维数组，排序右端点可以考虑结构体，加个重载<

解决核心问题：从存储的区间里挑选尽可能少的区间来覆盖一段区间。 那么首先左端点需要比该区间左端点<=才能做到覆盖。如果不行，就无解。然后还要在众多左端点比该区间左端点区间小的区间，使得该区间尽可能被覆盖多点（贪心思想体现）。即选右端点最大的，选完，待覆盖区间左端点为被选区间右端点，因为被覆盖了。重复挑选上述步骤，直至使得区间被覆盖，（能覆盖）或者区间遍历完，但仍为未覆盖。也就是无解。

综上所述：

两个边界点。第一个是待覆盖区间左端点，如果所能选区间里没有能覆盖的，（r < st) 那么无解。

第二个边界点。如果待覆盖区间被覆盖完（r>=ed)问题解决。或者，区间遍历完，仍不能使得完全被覆盖，则无解。

代码 

也可以用结构体弄个重载函数来实现区间存储和sort

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

const int N = 1e5+10;
// 二位数组存储区间
vector<vector<int>> a(N,vector<int>(2,0));

int main() {
    int st, ed;
    cin >> st >> ed;
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) {
        int l, r;
        cin >> l >> r;
        a[i][0] = l, a[i][1] = r;
    }
    //对左端点排序
    sort(a.begin(),a.begin()+n);
    
    int flag = 0, cnt = 0;
    
    for(int i = 0; i < n; i ++) {
        // 贪心：找<=要覆盖区间左端点，右端点覆盖能最大化的
        int j = i, r = -2e9;
        while(j < n && a[j][0]<=st) {
            r = max(r,a[j][1]);
            j ++;
        }
        // 覆盖不下去了，判断左边界
        if(r<st) {
            break;
        }
        // 找到一个区间覆盖一次。
        cnt ++;
        //判断 右边界
        if(r >= ed) {
            flag = 1;
            break;
        }
        //区间收缩
        st = r;
        i = j-1; // i结束循环会自增
    }
    if(flag) cout << cnt << endl;
    else cout << -1 << endl;
    
    return 0;
}