分析

区间覆盖是要用最少的区间完成对整个线段的全覆盖。核心思想是每次选择至少能覆盖要求的左端点且右端点最大的区间。

思路

① 将所有区间按照左端点排序
② 记前面所有区间没有覆盖到的第一个点为$pre$，那么接下来的区间一定要将$pre$覆盖，所以需要在后面所有区间中找出能覆盖$pre$且右端点最大的

模板题

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct range{
    int l, r;
    bool operator< (range &T){
        return l < T.l;
    }
}ranges[N];
int main(){
    int st, ed, n;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
        scanf("%d%d", &ranges[i].l, &ranges[i].r);
    sort(ranges, ranges + n);
    bool flag = false;
    int res = 0;
    for(int i = 0; i < n; i ++){
        int j = i, r = -2e9;
        while(ranges[j].l <= st && j < n){
            r = max(r, ranges[j].r);
            j ++;
        }
        if(r < st){
            break;
        }
        res ++;
        if(r >= ed){
            flag = true;
            break;
        }
        st = r;
        i = j - 1;
    }
    if(flag) printf("%d", res);
    else printf("-1");
    return 0;
}

小变式