python/TangDou/AcWing/Section/907.cpp

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100010;

struct Node {
    int l, r;
    const bool operator<(const Node &b) const { // 按每个区间的左端点从小到大排序
        return l < b.l;
    }
} range[N];

int n;      // n个区间
int st, ed; // 开始端点，结束端点
int res;    // 选择的区间数

int main() {
    // 输入
    cin >> st >> ed >> n;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};
    }
    // 1、按左端点从小到大排序
    sort(range, range + n);

    // 2、遍历每个区间,注意这里的i没有++,因为可能一次跳过多个区间
    for (int i = 0; i < n;) {
        int j = i;
        int r = -INF; // 预求最大，先设最小

        // 3、双指针，从当前区间开始向后，找出覆盖start起点的区间,就是让区间尽可能的长
        while (j < n && range[j].l <= st) {
            r = max(r, range[j].r); // 找出右端最长的那个区间
            j++;
        }
        // 4、如果没有找到，表示出现了空隙
        if (r < st) {
            cout << -1 << endl;
            exit(0);
        }
        // 5、如果找到，多找出了一个区间
        res++;

        // 6、如果已经完整覆盖,输出
        if (r >= ed) {
            cout << res << endl;
            exit(0);
        }
        // 7、更新迭代起点
        st = r;

        // 指针跳跃
        i = j;
    }
    // 7、如果运行到这里，表示无法覆盖掉所有点
    cout << -1 << endl;
    return 0;
}