学步园

题目分析：先将事情的起始时间和截止时间排序，把相互排斥的事情划到一个集合里。样例：

0   1   2  ；   3    3；     4    5      6      8；     10；    15    15

7   3   9  ；  4     8；    14   10   12    18；    15；    19     20

     ^              ^                       ^                          ^           ^

就会发现每个集合里，被选取的起始时间和截止时间最短的那个事情.....

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
	int s,e;
}arr[110];
int cmp(node x,node y)
{
	if(x.s==y.s)
		return x.e<y.e;
	else
		return x.s<y.s;
}
int main()
{
	int n,i;
	while(scanf("%d",&n)!=EOF&&n!=0)
	{
		for(i=1;i<=n;i++)
			scanf("%d %d",&arr[i].s,&arr[i].e);
		sort(arr+1,arr+1+n,cmp);
		int ts=arr[1].s;
		int te=arr[1].e;
		int ans=1;
		for(i=2;i<=n;i++)
		{
	            //寻找每一个集合里的最小一对
		    if(arr[i].s<te /*&& (arr[i].e-arr[i].s<te-ts)*/ )
		   {
			if(arr[i].e-arr[i].s<te-ts)
			{
			     ts=arr[i].s;
			     te=arr[i].e;
			  //printf("%d %d***\n",te,ts);
		       }
		  }
		  else
		 {
			ans++;
		        ts=arr[i].s;
		        te=arr[i].e;
			//printf("%d %d***\n",te,ts);
		}
	     }
	    printf("%d\n",ans);
	}
	//system("pause");
	return 0;
}