贪心 zoj3197

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 struct node
 9 {
10     int s,e;
11 }bn[5010];
12 
13 int main()
14 {
15     int T;
16     scanf("%d",&T);
17     while(T--)
18     {
19         for(int i=0;i<5000;i++)
20         {
21             bn[i].s=bn[i].e=0;
22         }
23         int n;
24         scanf("%d",&n);
25         for(int i=1;i<=n;i++)
26         {
27             scanf("%d%d",&bn[i].s,&bn[i].e);
28         }
29         int x=1;
30         int num=0;
31         while(x<=n)
32         {
33             int ma=x;
34             for(int i=1;i<=n;i++)
35             {
36                 if(bn[i].s<=x&&bn[i].e>=ma)
37                 {
38                     ma=bn[i].e;
39                 }
40             }
41             x=ma+1;
42             num++;
43         }
44         cout<<num<<endl;
45     }
46     return 0;
47 }
View Code