huchang.cpp

包括GRAY码

#include<fstream.h>
#include<time.h>



typedef struct
{
	int begin;
	int key;
	int end;
}Record;

int partition(Record a[],int p,int r )
{
	int i=p,
		j=r+1;
	Record x=a[p];
	while(true)
	{
		while(a[++i].begin<x.begin);
		while(a[--j].begin>x.begin);
		if(i>j)break;
		Record temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	a[p]=a[j];
	a[j]=x;
	return j;
}
void quicksort(Record a[],int p,int r)
{
	if(p<r)
	{
		int q=partition(a,p,r);
		quicksort(a,p,q-1);
		quicksort(a,q+1,r);
	}
}
void sort(Record a[],int r,int n)
{
	for(int i=r+1;i<n;i++)
	{
		Record temp=a[i];
		for( int j=i-1;j>=r&&a[j].key<temp.key;j--)
			a[j+1]=a[j];
		a[j+1]=temp;
	}
}


void main()
{
    int N;
    int k;
	int b,e;
	cout<<"input N:"<<endl;
	cin>>N;
	k=N;
    Record *a=new Record[N+1];
	for(int i=1;i<=N;i++)
	{
		 cout<<"input infor(b,e):"<<endl;
	     cin>>b>>e;
	     a[i].begin=b;
	     a[i].end=e;
	     a[i].key=1;
	}

 
    quicksort(a,1,N);
	/*for(i=1;i<(2*n);)
	{
		int j=i;
		while((a[j].time==a[j+1].time)&&(j<(2*n)))
			j++;
		sort(a,i,j+1);
		 i=j+1;
	}*/
	
	i=1;
	while(i<=N)
	{
		int j=i+1;
		for(int n=1;n<=i;n++)
			if(a[j].begin>=a[n].end)
			{a[i].end=a[j].end;
			k--;}
	    i++;
	}
	
	cout<<k<<endl;

		
}