最小区间覆盖

贪心思想

$poj2376$Cleaning Shifts

int n,m;
struct node{
    
    int l,r;
    bool operator<(const node&t)const{
    
        if(l == t.l) return r > t.r;
        return l < t.l;
    }
};
int main(){
    
    cin>>n>>m;
    vector<node> a(n+1);
    for(int i = 1;i <= n;i++){
    
        cin >> a[i].l >> a[i].r;
    }
    sort(a.begin()+1,a.end());
    int mr;
    int l = a[1].l, r = a[1].r;
    mr = r;
    if(l > 1){
    
        puts("-1");
        return 0;
    }
    int res = 1;
    int cnt = 2;
    
    while(cnt <= n && r < m){
    
        if(a[cnt].l > r+1){
    
            cout << -1 << endl;
            return 0;
        }
        while(a[cnt].l <= r+1 && cnt <= n && mr < m){
    
            mr = max(mr,a[cnt].r);
            cnt++;
        }
        r = mr;
        res++;
    }
    if(mr < m) puts("-1");
    else cout << res << '\n';
    return 0;
}