poj2376CleaningShifts（贪心）

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 using namespace std;
 7 #define N 26000
 8 struct Node
 9 {
10     int st,ed;
11 }p[N];
12 bool cmp(Node a,Node b){
13     if(a.st!=b.st)
14       return a.st<b.st;
15     return a.ed<b.ed;
16 }
17 int main()
18 {
19     int n,t;
20     while(scanf("%d%d",&n,&t)==2)
21     {
22         for(int i=0;i)
23         {
24             scanf("%d%d",&p[i].st,&p[i].ed);
25         }
26         
27         sort(p,p+n,cmp);
28         
29         int i=0;
30         int time=p[i].ed;
31         if(p[i].st!=1)
32         {
33             printf("-1\n");
34             continue;
35         }
36         i++;
37         while(i1)
38         {
39             time=p[i].ed;
40             i++;
41         }
42         int ans=1;
43         
44         while(time<t)
45         {
46             
47             if(i>=n)
48               break;
49             int tmp=i;
50             int w=p[i].ed;
51             i++;
52             while(i1)
53             {
54                 if(w<p[i].ed)
55                 {
56                     tmp=i;
57                     w=p[i].ed;
58                 }
59                 i++;
60             }
61             
62             if(w<=time || p[tmp].st>time+1)
63             { 
64                  break;    
65             }
66             else
67             {
68                 time=w;
69                 ans++;
70             }
71             
72         }
73         if(time<t)
74           ans=-1;
75         
76         printf("%d\n",ans);
77     }
78     return 0;
79 }