题意:在几个区间里面,挑选出几个数字组成一个集合,使得每个区间都至少有两个数字在这个集合里面,求这个集合的最少数字个数。

题解:贪心法,先对区间排序下,以右端点排序,把每个区间扫一遍过去,看区间内有几个元素在当前集合中。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include <string>
 8 #include <set>
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 using namespace std;
16 #define PI acos( -1.0 )
17 typedef long long ll;
18 typedef pair<int,int> P;
19 const double E = 1e-8;
20 
21 const int NO = 10000 + 5;
22 int a[NO<<1];
23 int n;
24 struct ND
25 {
26     int start, en;
27 }st[NO];
28 
29 bool cmp( const ND &a, const ND &b )
30 {
31     return a.en < b.en;
32 }
33 
34 int main()
35 {
36     while( ~scanf( "%d",&n ) )
37     {
38         for( int i = 0; i < n; ++i )
39             scanf( "%d%d", &st[i].start, &st[i].en );
40         sort( st, st+n, cmp );
41         int cur = 0;
42         a[cur++] = st[0].en-1;
43         a[cur++] = st[0].en;
44         for( int i = 1; i < n; ++i )
45         {
46             int num = 0;
47             for( int j = 0; j < cur; ++j )
48                 if( st[i].start <= a[j] && st[i].en >= a[j] )
49                 {
50                     ++num;
51                     if( num >= 2 )
52                         break;
53                 }
54             if( num == 0 )
55             {
56                 a[cur++] = st[i].en-1;
57                 a[cur++] = st[i].en;
58             }
59             if( num == 1 )
60                 a[cur++] = st[i].en;
61         }
62         printf( "%d\n", cur );
63     }
64     return 0;
65 }
View Code