zju1076.cpp

zoj solved 今年在zoj上a的题目

//zju1076 07.10.01
#include <stdio.h>
#include <string.h>

struct{
	int a;
	int b;
	int index;
}exon[1001],temp;

int s[1001],t[1001];

int main()
{
	int i,j,k;
	int sum,max;
	int n;
	while(scanf("%d",&n) != EOF && n != 0)
	{
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&exon[i].a,&exon[i].b);
			//exon[i].len=1;
			exon[i].index=i+1;
		}
		for(i=0;i<n-1;i++)
		{
			k=i;
			for(j=i+1;j<n;j++)
			{
				if(exon[j].a<=exon[k].a) k=j;
			}
			if(k!=i)
			{
				temp=exon[i];
				exon[i]=exon[k];
				exon[k]=temp;
			}
		}
		max=0;
		for(i=0;i<n;i++)
		{
			sum=1;
			temp=exon[i];
			k=0;
			s[k++]=i;
			for(j=i+1;j<n;j++)
			{
				if(temp.b<=exon[j].a) 
				{
					s[k++]=j;
					temp=exon[j];
					sum++;
				}
			}
			if(max<sum)
			{
				max=sum;
				for(i=0;i<max;i++)
				{
					t[i]=s[i];
				}
			}
		}
		//printf("%d",exon[t[0]].index);
		for(i=0;i<max-1;i++)
		{
			printf("%d ",exon[t[i]].index);
		}
		printf("%d\n",exon[t[max-1]].index);
	}

	return 0;
}