区间类贪心问题

区间选点

贪心流程：在 $cnt$ 个区间中确定点，这些区间没有交集，且被选出的点包含于所有区间。

证明：设算法得到答案是 $cnt$，最优解是 $ans$。

1. $ans \leq cnt$：由定义可知。
2. $ans \geq cnt$：对于被选点的 $cnt$ 个区间，这些区间没有交集，所以需要至少 $cnt$ 个点选出这些区间，即 $ans \geq cnt$。

所以 $ans = cnt$，贪心策略正确。

方法有两种：1. 排序右端点，按照右端点从小到大枚举区间，如果区间已经包含点跳过，否则选择当前区间的右端点。2. 排序左端点，按照左端点从大到小枚举区间，如果区间已经包含点跳过，否则选择当前区间的右端点。

//  方法一
#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 () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n; i ++ ) {
        cin >> range[i].l >> range[i].r;
    }

    sort (range, range + n);

    int ed = -0x3f3f3f3f, res = 0;
    for (int i = 0; i < n; i ++ ) {
        if (range[i].l > ed) {
            res ++ ;
            ed = range[i].r;
        }
    }

    cout << res << "\n";

    return 0;
}


//  方法二
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

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

int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n; i ++ ) {
        cin >> range[i].l >> range[i].r;
    }

    sort (range, range + n);

    int ed = 0x3f3f3f3f, res = 0;
    for (int i = n - 1; i >= 0; i -- ) {
        if (range[i].r < ed) {
            res ++ ;
            ed = range[i].l;
        }
    }

    cout << res << "\n";

    return 0;
}

最大不相交区间数量

贪心思路：每个区间右端点排序，从左至右依次选出第一个没有被覆盖的区间。

证明：设算法得到的答案是 $cnt$，最优解是 $ans$。

1. $ans \geq cnt$：根据定义可以得出。
2. $ans \leq cnt$：反证法：假设 $ans > cnt$，则最多可以选 $ans$ 个不相交的区间。覆盖这 $ans$ 个不相交的区间，至少需要 $ans$ 个点；对于所有区间，覆盖所有区间只需要 $cnt$ 个点。$ans \geq cnt$ 得证。

所以 $ans = cnt$，此算法答案为正解。

#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 () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n; i ++ ) {
        cin >> range[i].l >> range[i].r;
    }

    sort (range, range + n);

    int ed = -0x3f3f3f3f, res = 0;
    for (int i = 0; i < n; i ++ ) {
        if (range[i].l > ed) {
            res ++ ;
            ed = range[i].r;
        }
    }

    cout << res << "\n";

    return 0;
}

区间分组

贪心流程：左端点从小到大排序，一次选每一个区间，如果存在某一个组内最右边端点比该区间左端点小，放入该组；否则，新建一个组。

证明：设算法得到的答案是 $cnt$，最优解 $ans$。

1. $ans \leq cnt$：根据定义可以得出。
2. $ans \geq cnt$：在选某一个区间需要新建一个组时，现有的所有组的最大右端点都比当前区间的左端点小，那么至少需要 $cnt$ 个区间，所以 $ans \geq cnt$。

所以 $ans = cnt$，此算法答案为正解。

#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

constexpr int N = 1E5 + 10;

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

int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 0; i < n; i ++ ) {
        int l, r;
        cin >> l >> r;
        ranges[i] = {l, r};
    }

    sort (ranges, ranges + n);

    priority_queue <int, vector <int>, greater <int>> heap;

    for (int i = 0; i < n; i ++ ) {
        auto u = ranges[i];
        if (!heap.size () || heap.top () >= u.l) {
            heap.push (u.r);
        } else {
            heap.pop ();
            heap.push (u.r);
        }
    }

    cout << heap.size ();

    return 0; 
}

区间覆盖

贪心流程：区间左端点从小到大排序，从小到大枚举每个区间，在能覆盖 $start$ 的区间中，选择右端点最大的区间，将 $start$ 更新成该区间的右端点。

证明：设算法得到的答案是 $cnt$，最优解 $ans$。

1. $ans \leq cnt$：根据定义可以得出。
2. $ans \geq cnt$：调整法，在最优解与算法不同的区间，其能覆盖 $start$ 且 $r_{ans} < r_{cnt}$。则都可以将最优解的区间替换成算法的解，所以 $ans \geq cnt$。

所以 $ans = cnt$，此算法答案为正解。

#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

constexpr int N = 1E5 + 10, inf = 1E9;

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

int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int st, ed;
    cin >> st >> ed;

    cin >> n;

    for (int i = 0; i < n; i ++ ) {
        int l, r;
        cin >> l >> r;
        ranges[i] = {l, r}; 
    }

    sort (ranges, ranges + n);

    int res = 0;
    bool success = false;

    for (int i = 0; i < n; i ++ ) {
        int j = i, r = -inf;
        while (j < n && ranges[j].l <= st) {
            r = max (r, ranges[j].r);
            j ++ ;
        }

        if (r < st){
            res = -1;
            break;
        }

        res ++ ;

        if (r >= ed) {
            success = true;
            break;
        }

        st = r;
        i = j - 1;
    }

    if (!success) {
        res = -1;
    }

    cout << res << "\n";

    return 0; 
}