区间覆盖

AcWing-907-区间覆盖

实现

#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
#define end EnD
using namespace std;

const int N = 100010;
struct node {
    int l, r;
    bool operator < (const node& o) const {
        return l < o.l;
    }
};
int n, beg, end;
node a[N];

int main () {
    cin >> beg >> end >> n; // [beg, end]
    for (int i = 1; i <= n; ++ i) cin >> a[i].l >> a[i].r;

    sort(a + 1, a + n + 1);
    int res = 0;
    bool flag = false;
    for (int i = 1; i <= n; ++ i) {
        int j = i, max_r = -inf;
        while (j <= n && a[j].l <= beg) {
            max_r = max(max_r, a[j].r);
            ++ j;
        }
        if (max_r < beg) {
            flag = false;
            break;
        }
        ++ res;
        if (max_r >= end) {
            flag = true;
            break;
        }
        beg = max_r;
        i = j - 1;
    }
    cout << res << endl;
    return 0;
}