Acwing 区间问题-Acwing 907.区间覆盖

实现思路：
设线段的左端点为start，右端点为end

• 所有区间按照左端点从小到大排序
• 从前往后依次枚举每个区间，在所有能覆盖start的区间中，选择一个右端点最大的区间，随后，将start更新为选中区间的右端点。当start >= end，结束
• 用双指针算法来找左端点<start，且右端点最大的区间，若找到的右端点依旧小于start，即无解；否则区间数量+1，且更新start
• 注意：一轮过后i=j-1，j是满足条件的区间，为了避免一些不必要的i枚举，所以i可以跳到满足条件的区间继续向后，但因为一轮后i++，所以先-1，下一轮就从j开始，这样又不会缺少或跳过满足的区间

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>  
#include <queue>
using namespace std;

const int N = 100010;  

int n;  

struct Range {
    int l, r;  // l 表示区间左端点, r 表示区间右端点
    // 重载小于运算符，用于将区间按照左端点 l 进行升序排序
    bool operator< (const Range &W) const {
        return l < W.l;  // 按左端点 l 从小到大排序
    }
} range[N];  // 定义一个大小为 N 的 Range 数组来存储区间

int main() {
    int start, end;
    cin >> start >> end;  
    cin >> n;  

   
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};  // 将左端点和右端点存入 range 数组
    }

    // 对区间按照左端点 l 进行升序排序
    sort(range, range + n);

    int res = 0;          // 结果变量，记录需要选择的区间数量
    bool success = false; // 表示是否能够找到满足条件的解

    // 遍历每个区间
    for (int i = 0; i < n; i++) {
        int j = i, r = -2e9;  // r 用来记录当前覆盖的最大右端点
        // 寻找所有能够与当前 start 相交的区间
        while (j < n && range[j].l <= start) {
            r = max(r, range[j].r);  // 更新能覆盖的最远右端点
            j++;  // 继续往后找
        }

        // 如果找不到一个右端点能够覆盖当前 start，说明无解
        if (r < start) break;

        // 找到一个合适的区间，区间数量加 1
        res++;

        // 如果右端点已经能够覆盖到 end，说明找到了解
        if (r >= end) {
            success = true;
            break;
        }

        // 更新新的起点为当前找到的最远右端点，继续寻找下一个区间
        start = r;
        i = j - 1;  // 更新 i 的位置
    }

    cout << (success ? res : -1) << endl;

    return 0;
}

以上就是几个经典的区间问题，重点在于思路的证明（不行就试）