poj 1716(贪心)

题意：给出数轴上的n个区间，每个区间都是连续的int区间。现在要在数轴上任意取一堆元素，构成一个元素集合V，要求每个区间和元素集合V的交集至少有两个不同的元素求集合V最小的元素个数。

解题思路：

考虑到区间之间的重叠性，所以每次都要尽可能地去每个区间靠后的值，才能保证前后两个区间公共的元素最多，其实把握了这个思想后就是个简单的贪心思想了。一开始我是拿每个区间的开始端进行排序，结果WA。。。后面才想到，如果两个区间是包含的关系，那么这样会出现问题。

AC:

#include<iostream>
#include<algorithm>
using namespace std;

typedef class
{
public:
	int s,e;
}interval;      //间隔（区间）

int cmp(const void* a,const void* b)
{
	interval* x=(interval*)a;
	interval* y=(interval*)b;
	return (x->e) - (y->e);  //对区间按末端点排序
}

int main(void)
{
	int n; //区间数
	while(cin>>n)
	{
		interval* inter=new interval[n];

		for(int i=0;i<n;i++)
			cin>>inter[i].s>>inter[i].e;
		qsort(inter,n,sizeof(interval),cmp);  //对区间按末端点排序
		int Selem=inter[0].e-1 , Eelem=inter[0].e;  //当前区间所取的两个元素，初始化为第0个区间最后两个元素
		int sum=2;  //至少取sum个元素才能保证每个区间至少含有其中的2个元素
		for(int k=1;k<n;k++)
			if(inter[k].s<=Selem)  //前一个区间所取的两个元素都在当前区间内
				continue;  //则当前区间无需取任何元素
			else if(inter[k].s<=Eelem)  //前一个区间所取的只有一个元素在当前区间内
			{
				Selem=Eelem;
				Eelem=inter[k].e;  //按序更新当前区间所取的两个元素：Selem与Eelem
				sum++;  //Eelem是新取的一个元素
			}
			else  //前一个区间所取的没有一个元素在当前区间内
			{
				Selem=inter[k].e-1;
				Eelem=inter[k].e;  //按序更新当前区间所取的两个元素：Selem与Eelem
				sum+=2;  //Selem与Eelem是新取的两个元素
			}
		cout<<sum<<endl;
		delete inter;
	}
	return 0;
}