POJ 2376

连接点应该是只需连接而不必覆盖。

按开始时间排序。

假设当前最远为t，则按序枚举在t+1范围内开始的cow即可，再求出最远点。注意break条件。

 1 #include <cstdio> 
 2 #include <iostream> 
 3 #include <cstring>  
 4 #include <cctype>  
 5 #include <algorithm>  
 6 #define LL unsigned __int64
 7 using namespace std; 
 8 
 9 const int N= 25100;
10 
11 struct Cow{
12     int s,e;
13     bool operator < (const Cow &a)const{
14         if(s<a.s) return true;
15         return false;
16     }
17 }cow[N];
18 int n,T;
19 
20 int main(){
21     while(scanf("%d%d",&n,&T)!=EOF){
22         for(int i=0;i<n;i++){
23             scanf("%d%d",&cow[i].s,&cow[i].e);
24         }
25         sort(cow,cow+n);
26         int i=0,t=0,j;
27         int ans=0;
28         if(cow[i].s>1){
29             puts("-1");
30             continue;
31         }
32         while(i<n&&t<T){
33             j=-1;
34             while(i<n&&cow[i].s<=t+1){
35                 j=max(j,cow[i].e);
36                 i++;
37             }
38             if(j<=t) break;
39             t=j;
40         //    cout<<t<<endl;
41             ans++;
42         }
43         if(t<T){
44             printf("-1
");
45         }
46         else printf("%d
",ans);
47     }
48     return 0;
49 }

View Code