POJ 2376

 1 #include<iostream>//by chengdacaizi.
 2 #include<stdio.h>
 3 #define MAXN 25005
 4 using namespace std;
 5 
 6 struct Cows 
 7 {
 8     int begin;
 9     int end;
10 };
11 
12 Cows cow[MAXN];
13 
14 int compare(const void * i,const void * j);
15 int main()
16 {
17     //freopen("acm.acm","r",stdin);
18     int i;
19     int j;
20     int n;
21     int t;
22     bool boo;
23     int last;
24     int max;
25     int tem;
26     int max_num;
27     int result;
28     scanf("%d %d",&n,&t);
29     for(i = 0; i < n; ++ i)
30     {
31         scanf("%d %d",&cow[i].begin,&cow[i].end);
32     }
33     qsort(cow,n,sizeof(Cows),compare);
34     last = 1;
35     i = 0;
36     max = 0;
37     result = 0;
38     boo = true;
39     while(1)
40     {
41         max = -1;
42         while(cow[i].begin <= last)
43         {
44             if((tem = cow[i].end - last) > max)
45             {
46                 max = tem;
47                 max_num = i;
48             }
49             ++ i;
50         }
51         if(max == -1)
52         {
53         //    cout<<cow[i].begin<<"   000000000000"<<endl;//很巧合的处理，当数组越界的时候，当然，还没有完成，那么自动跳出，cout<<-1；
54             boo = false;
55             break;
56         }
57         ++ result;
58         if(cow[max_num].end >= t)
59         {
60             break;
61         }
62         else
63         {
64             last = cow[max_num].end + 1;
65         }
66     }
67     if(boo)
68         cout<<result<<endl;
69     else
70         cout<<-1<<endl;
71 
72 }
73 
74 int compare(const void * i,const void * j)
75 {
76     return *((int *)i) - *((int *)j);
77 }