1.区间选点问题

问题

给定 n个区间，最少选择多少个点，可以保证每个区间至少包含一个选择的点

2. 最大不相交的区间数目

问题

给定 n个区间，从中选择若干个区间互不相交，最多可以选择多少个区间

贪心步骤

step1: 所有区间按照右端点排序
step2: 依次遍历每个区间
（1）如果当前区间包含点，则跳过
（2）否则，当前区间不包含已选点，则把当前区间的右端点加入答案

代码模板

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

struct Seg{
    int l, r;

    bool operator<(const struct Seg& b){
        return r <= b.r;
    }
}segs[N];

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

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

    sort(segs, segs + n);

    int ans = 0;
    int cur = -2e9;
    for(int i = 0; i < n; i++){
        if(segs[i].l <= cur && segs[i].r >= cur){
            continue;
        } else {
            cur = segs[i].r;
            ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

3. 区间分组

问题

给定 n个区间，分成若干组，使得组内区间互不相交，问最少可以分成几组

贪心步骤

step1: 所有区间按照左端点从小到大排序
step2: 依次遍历所有区间
判断当前区间能够加入任一组内
（1）加入可以加入某一个组内（条件：组内所有区间的最大右端点max_r < cur.l）,则加入其中
（2）否则，不能加入任一个组内（条件：当前区间和所有的区间都相交), 则开新组，加入其中

代码模板

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;


const int N = 100010;

struct Seg{
    int l, r;
    bool operator<(struct Seg& b){
        return l < b.l;
    }
}segs[N];

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

    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        segs[i] = {a, b};
    }

    // 左端点排序
    sort(segs, segs + n);

    int ans = 0;
    priority_queue<int, vector<int>, greater<int>> q;

    for(int i = 0; i < n; i++){
        if(q.size() == 0){
            int max_r = segs[i].r;
            q.push(max_r);
            ans++;
        } else {
            //找到一个组，使得所有区间的最右端点Max_r < segs[i].l
            int max_r = q.top();
            if(max_r < segs[i].l){
                q.pop();
                q.push(segs[i].r);
            } else {
                //当前区间和所有组都有交集，新开一个组
                q.push(segs[i].r);
                ans++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

4. 区间覆盖

问题

给定 n个区间，一个线段 [st, ed], 问最少需要多少个区间可以完全覆盖线段 [st, ed]

贪心步骤

step1: 所有区间按照左端点从小到大排序
step2: 依次遍历每个区间，寻找所有能覆盖st的区间，从中选择右端点最大的区间加入答案，然后更新st到右端点最大值

代码模板

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>

using namespace std;
const int N = 100010;

struct Seg{
    int l, r;
    bool operator<(const Seg& w){
        return l < w.l;
    }
}segs[N];

int main()
{
    int st, ed;
    cin >> st >> ed;

    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        segs[i] = {a, b};
    }
    sort(segs, segs + n);

    int ans = 0;
    bool flag = false;
    for(int i= 0; i < n;){

        int j = i;
        int tmp = -2e9;
        for(; j < n; j++){
            if(segs[j].l > st) break;
            tmp = max(tmp, segs[j].r);
        }
        //cout << "st=" << st << ", tmp=" << tmp <<",l=" << i << ",r=" << j - 1 << endl;

        //st 无法覆盖
        if(tmp < st){
            ans = -1;
            break;
        }
        // st完成覆盖
        ans ++;
        if(tmp >= ed){
            flag = true;
            break;
        }

        st = tmp;
        i = j;
    }

    if(flag == false) ans = -1;
    cout << ans << endl;

    return 0;
}