2 条题解

  • 0
    @ 2025-10-27 21:21:47

    #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;
    

    }

    信息

    ID
    5475
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    24
    已通过
    6
    上传者