HDOJ 2037 今年暑假不AC （贪心）

1 //http://acm.hdu.edu.cn/showproblem.php?pid=2037


 1 //贪心问题:选择不相交的区间问题
 2 
 3 
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 typedef struct _NODE_        //结构体 
 9 {
10     int Ti_s;
11     int Ti_e;
12     
13 }Node;
14 
15 Node TV[101];
16 
17 int cmp(Node x,Node y)    //排序规则 
18 {
19     return x.Ti_e < y.Ti_e;
20 }
21 
22 int main()
23 {
24     int N,i,temp,count;
25     while(scanf("%d",&N)!=EOF && N)        
26     {
27         for(i=0;i<N;i++)
28         {
29             scanf("%d%d",&TV[i].Ti_s,&TV[i].Ti_e);
30         }
31         sort(TV,TV+N,cmp);            //根据结束时间的大小进行排序 
32         
33         temp = TV[0].Ti_e;
34         count = 1;
35         //***************贪心部分****************
36         for(i=1;i<N;i++)            
37         {
38             if(TV[i].Ti_s >= temp)
39             {
40                 count++;
41                 temp = TV[i].Ti_e;
42             }
43     //        temp = TV[i].Ti_e;
44         }
45         //***************贪心部分**************** 
46         
47         printf("%d
",count);        
48     }
49     return 0;
50 }