POJ 2376 Cleaning shifts 贪心 基础题

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 const int maxn=25000+3;
 8 const int inf=0x3f3f3f3f;
 9 
10 struct Edge
11 {
12     int l,r;
13 }edge[maxn];
14 
15 bool cmp(Edge a,Edge b)
16 {
17     if(a.l==b.l)
18         return a.r<b.r;
19     else
20         return a.l<b.l;
21 }
22 
23 int solve(int N,int T)
24 {
25     sort(edge,edge+N,cmp);
26 
27     int ret=0;
28     int cnt=1;
29     int i=0;
30     while(true)
31     {
32         int maxl=cnt-1;
33 
34         for(;i<N;i++)
35         {
36             if(edge[i].l<=cnt&&edge[i].r>=cnt)
37                 maxl=max(maxl,edge[i].r);
38             if(edge[i].l>cnt)
39                 break;
40         }
41 
42         if(maxl<cnt)
43             return -1;
44         ret++;
45         cnt=maxl+1;
46         if(cnt>T)
47             return ret;
48     }
49 }
50 
51 int main()
52 {
53     int N,T;
54     while(~scanf("%d%d",&N,&T))
55     {
56         for(int i=0;i<N;i++)
57         {
58             scanf("%d%d",&edge[i].l,&edge[i].r);
59         }
60 
61         printf("%d\n",solve(N,T));
62     }
63     return 0;
64 }