Acwing907 区间覆盖

贪心

#include <bits/stdc++.h>
using namespace std;
int n;
#define MAXN 100010
int a[MAXN],b[MAXN];
int st,ed;

struct Range{
    int l,r;
    bool operator < (Range& w){
        if(l==w.l) return r>w.r;
        return l<w.l;
    }
}range[MAXN];

int main(){
    cin>>st>>ed;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>range[i].l>>range[i].r;
    }
    sort(range,range+n);
    int res =0 ;
    bool success = false;
    for(int i=0;i<n;i++){
        int j = i,r = -2e9;
        while(j<n && range[j].l<=st) {
            r = max(r,range[j].r);
            j++;
        }
        if(r<st) break;
        res++;
        if(r>=ed){
            success = true;
            break;
        }
        st = r;
        i = j-1;
    }
    if(!success) res=-1;
    printf("%d\n",res);

    return 0;
}