题意：在几个区间里面，挑选出几个数字组成一个集合，使得每个区间都至少有两个数字在这个集合里面，求这个集合的最少数字个数。
题解：贪心法，先对区间排序下，以右端点排序，把每个区间扫一遍过去，看区间内有几个元素在当前集合中。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cctype> 6 #include <time.h> 7 #include <string> 8 #include <set> 9 #include <map> 10 #include <queue> 11 #include <vector> 12 #include <stack> 13 #include <algorithm> 14 #include <iostream> 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 ", cur ); 63 } 64 return 0; 65 }