/* * POJ-1716.cpp * * Created on: 2013年11月19日 * Author: Administrator */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn = 10010; struct node{ int x; int y; bool operator<(const node& b)const{ return y < b.y; } }a[maxn]; bool vis[maxn]; /** * 本题的题意是: * 在几个区间中选择几个数,加入到集合中,使得每个区间至少有两个数出现在集合中... * 求这个集合最小有多少个数 * * 解题策略:贪心 * 贪心选择旺旺发生在极端选择处,这个思想和POJ1328那道雷达的题目的思想是一样的... * 先对区间按右端点进行排序。然后从左往右判断该区间中是否已经有2个元素出现在集合中. * 如果没有选择最右的端点加入到集合..(为什么选择右端点加入到集合而不是选择左端点呢???举一个例子: * 在(1,3)、(2,5)这两个区间中,很明显选择3加入到集合中能使集合中的元素的个数尽可能的少) */ int main(){ int n; while(scanf("%d",&n)!=EOF){ int i; for(i = 0 ; i < n ; ++i){ scanf("%d%d",&a[i].x,&a[i].y); } memset(vis,false,sizeof(vis)); sort(a,a+n); int count = 2; vis[a[0].y] = true; vis[a[0].y - 1] = true; int j; for(i = 1 ; i < n ; ++i){ int m = 0; for(j = a[i].x ; j <= a[i].y ; ++j){//判断第i个区间赢有多少个数出现在集合中 if(vis[j]){ m++; } if(m >= 2){//如果这个区间已经有2个数出现在集合中,则已经满足条件,跳出本层循环 break; } } if(m == 0){//如果这个区间没有数出现在集合中,则选择最后两个数加入到集合中 count += 2; vis[a[i].y] = true; vis[a[i].y - 1] = true; } if(m == 1){//如果这个区间只有一个数出现在集合中,则选择最后一个数加入到集合中 count += 1; vis[a[i].y] = true; } } printf("%d\n",count); } return 0; }