(Relax 贪心1.7)POJ 1716 Integer Intervals

/* 
 * POJ-1716.cpp 
 * 
 *  Created on: 2013年11月19日 
 *      Author: Administrator 
 */  
  
#include   
#include   
#include   
#include   
  
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;  
}