【hdoj_2037】今年暑假不AC

题目：http://acm.hdu.edu.cn/showPRoblem.php?pid=2037

可以这样理解题意：将每个节目看做是一个区间，起始时间为左右端点，待求的是：最多可以有多少个区间互不相交(注意:[3,5]和[5,7]虽有共同的端点，但是是不相交的).

思路:所选择的区间长度(节目时间长短)越小，余下的空余区间就越多，所以长度小的区间，应该先被选中.因此，步骤如下：

step1.对所有的区间按照区间长度递增的顺序排序.

step2.依次考察每个区间，看看这个区间与已经选中的区间是否相交，如果都不相交，则这个区间被选中，否则不能选择这个区间.以此类推，直至考察完所有区间.

例如，题目中的一个例子，解答如下图

C++代码如下:

#include<iostream>#include<algorithm>using namespace std;struct TV//结构体 {	int s;	int e;}; bool cmp(TV tv1,TV tv2)//作为sort函数的一个参数，以便进行结构体排序{			//这个函数决定了排序的原则：按照节目时间递增排序 ——贪心 	return tv1.e-tv1.s < tv2.e - tv2.s;}int main(){		int n;	while(1)	{		cin >> n;//节目总数 		if(n==0)			break;		TV * tv = new TV[n];		for(int i=0;i<n;i++)			cin >> tv[i].s >> tv[i].e;//节目起始时间 		sort(tv,tv+n,cmp);//排序，根据cmp函数可知，是按照节目时间长短递增排序的 		int * IndexOfOk = new int[n];//被选中要看的节目下标 		int NumOfOk = 0;//被选中要看的节目个数 		for(int i=0;i<n;i++)//针对每个节目 		{					//看看是否可以被选中，原则是不与已经选中的节目的时间冲突 			int ok = 1;			for(int k=0;k<NumOfOk;k++)//IndexOfOk[0~NumOfOk-1]记录了已经选中的节目的下标 				if(!(tv[IndexOfOk[k]].s>=tv[i].e || tv[i].s>=tv[IndexOfOk[k]].e))// 如果时间冲突 				{					ok = 0;					break;				}			if(ok)//如果ok=1，表明节目i与已经选中的所有的节目都不冲突，则可以加入它们 				IndexOfOk[NumOfOk++] = i;//记录下它的下标，并且数目++ 		}		cout << NumOfOk << endl; 	}	return 0;}注意：上述代码提交会出现错误提示，删掉所有的注释再提交，可以通过.
总结：
1.结构体的使用不必过于复杂，写上数据成员即可.
2.sort()中的函数参数决定了如何排序.
3.注意中IndexOfOK[]数组的用法.