经典区间问题的贪心解法

最大不相交区间数量

leetcode 435 无重叠的子区间

给定一个区间的集合 A ，其中 A[i] = [starti​,endi​]。返回需要移除区间的最小数量，使剩余区间互不重叠。

//题目的完整代码
struct Intervals{
    int st, ed;
} a[100005];

bool cmp(Intervals x, Intervals y) {
    return x.ed < y.ed;
}

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        for (int i = 0; i < n; i++) {
            a[i].st = intervals[i][0];
            a[i].ed = intervals[i][1];
        }

        sort(a, a + n, cmp);

        int sum = 1, st = a[0].st, ed = a[0].ed;
        for (int i = 1; i < n; i++) {
            if (a[i].st >= ed) {
                sum++;
                st = a[i].st;
                ed = a[i].ed;
            }
        }
        return n - sum;
    }
};

区间分组

给定 N 个闭区间 [ai​,bi​]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。 输出最小组数。

我们可以把所有开始时间和结束时间排序，遇到开始时间就把需要的教室加 1，遇到结束时间就把需要的教室减 1，在一系列需要的教室个数变化的过程中，峰值就是多同时进行的活动数，也是我们至少需要的教室数。

//题目的完整代码
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n;
int b[2*N], idx;

int main(){
    scanf ("%d", &n);
    for (int i = 0; i < n; i ++) {
        int l, r;
        scanf("%d %d", &l, &r);
        b[idx ++] = l * 2;//标记左端点为偶数。
        b[idx ++] = r * 2 + 1;// 标记右端点为奇数。
    }

    sort(b, b + idx);

    int res = 1, t = 0;
    for (int i = 0; i < idx; i ++){
        if(b[i] % 2 == 0) t ++;
        else t --;
        res = max(res, t);
    }
    printf ("%d\n", res);
    return 0;
}

最小区间覆盖

给定 N 个闭区间 [ai​,bi​]以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出 −1。

分析： 第一步，将所有区间按照左端点从小到大进行排序 第二步，从前往后枚举每个区间，在所有能覆盖start的区间中，选择右端点的最大区间，然后将start更新成右端点的最大值

//题目的完整代码
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

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

int main(){
    int st, ed;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ){
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    sort(range, range + n);

    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i ++ ){
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st){
            r = max(r, range[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;
    printf("%d\n", res);

    return 0;
}

找拐点

求一个最长序列，使得该序列的任意三个相邻元素，中间的元素是三个中最大的，或者是最小的（最长波浪序列）

//题目的完整代码
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];

    int x = 0;
    while (x+1 < n and h[x+1] == h[x]) ++x; // 开始如果一段相同的则去重，取哪盆都一样

    bool f = false;
    if (h[x+1] > h[x]) f = true; // 确定一开始是上升还是下降的

    int ans = 1;
    for (int i = x+1; i < n; ++i) {
        if (i == n-1) ans++; // 结尾没有拐点直接加
        else if (f && h[i+1] < h[i]) { ans++; f = 0; } // 找到波峰
        else if (!f && h[i+1] > h[i]) { ans++; f = 1; } // 找到波谷
    }

    cout << ans << '\n';

    return 0;
}