最小区间覆盖

贪心思想

poj 2376poj \ 2376 Cleaning Shifts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
}