今年暑假不AC (贪心)

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 
 7 
 8 using namespace std;
 9 
10 struct node
11 {
12     int start;    // 开始时间 
13     int end;    // 结束时间 
14 }a[101];
15 
16 bool cmp(node a, node b)  
17 {
18     return a.end <= b.end;
19 } 
20 
21 int main() 
22 {
23     int n;
24     while(cin >> n && n != 0)
25     {
26         for(int i = 0; i < n; ++i)
27             cin >> a[i].start >> a[i].end;
28         
29         sort(a, a+n, cmp);             // 按结束时间从小到大排序
30         
31         int ans = 1;                   // 假设已经选了第一个最优解 
32         int lastEnd = a[0].end;        // 保存上一个最优解的区间end值 
33         for(int i = 1; i < n; ++i)    // 从第二个最优解开始选 
34         {    
35             if(a[i].start >= lastEnd)
36             {
37                 ans++;    
38                 lastEnd = a[i].end;
39             }     
40         } 
41         cout << ans << endl; 
42     }
43     
44             
45     return 0;
46 }