POJ 2376

题意略。

思路：

本题有几个坑：

1.[1,5] , [6,10] 是对 [1,10] 的全覆盖，所以我们要把区间变为[1,6)和[6,11)，最后判断连续区间右端是否大于T。

2.牛的工作时间可能会超过T，要及时跳出循环。

3.区间有可能左端没有覆盖到1。

代码如下：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 25005;

struct seg{
    int l,r;
    seg(int l = 0,int r = 0){
        this->l = l,this->r = r;
    }
};

int N,T;
seg store[maxn];

bool cmp(const seg& s0,const seg& s1){
    if(s0.l != s1.l) return s0.l < s1.l;
    return s0.r > s1.r;
}

int main(){
    scanf("%d%d",&N,&T);
    int l,r;
    for(int i = 0;i < N;++i){
        scanf("%d%d",&l,&r);
        r += 1;
        store[i] = seg(l,r);
    }
    
    sort(store,store + N,cmp);
    int rbound = -1,ans = 0,lft,rmax,i;
    for(i = 0,rmax = store[0].r,lft = store[0].l;i < N;++i){
        l = store[i].l,r = store[i].r;
        if(rbound == -1 || l > rbound){
            ++ans;
            rbound = rmax;
        }
        if(rbound > T || rbound < l) break;
        rmax = max(rmax,r);
    }
    if(lft > 1 || rmax <= T) ans = -1;
    else if(rbound <= T && rmax > T) ans += 1;
    
    printf("%d
",ans);
    return 0;
}