编程之美2.19区间重合判断

 

/*
 *  区间重合判断
 *  比如,给出待判断区间[x,y]如[1,6],以及目标区间[x1, y1],[x2,y2]....[xi, yi](如[2,3] [1,2] [3, 9]),
 *  判断[1,6]是否在目标区间中
 *
 *  做法: 先把根据各个目标区间的第一个元素xi排序(可用快排),然后将目标区间中可以合并的区间进行合并,然后
 *        在目标区间的xi中用二分查找来找待判断区间中的x,然后再判断y
 * */

#include <iostream>
using namespace std;
//sort
int partation(int low,int high,int *a,int *b) //对区间进行二次排序
{
	int par=a[low];
	int par1=b[low];
	while(low<high)
	{
		while(low<high&&a[high]>=par)
			high--;
		a[low]=a[high];
		b[low]=b[high];
		while(low<high&&a[low]<=par)
			low++;
		a[high]=a[low];
		b[high]=b[low];
	}
	a[low]=par;
	b[low]=par1;
	return low;
}

void quicksort(int low,int high,int *a,int *b)
{
	if(low<high)
	{
		int par=partation( low, high, a,b);
		quicksort(low,par-1,a,b);
		quicksort(par+1,high,a,b);
	}
}

void Quick(int *a,int*b,int length)
{
	quicksort(0,length-1,a,b);
	for(int i=0;i<length;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	for(i=0;i<length;i++)
		cout<<b[i]<<" ";
	cout<<endl;
}

//unite
void unite(int *a,int*b,int*c,int*d,int length,int& number)
{
	int temp=0;
	c[temp]=a[0];
	for(int i=1;i<=length-1;i++)
	{
		if(b[i-1]>=a[i])
			continue;
		d[temp++]=b[i-1];
		c[temp]=a[i];
	}
	d[temp]=b[length-1];
	number=temp+1;
	for(i=0;i<=temp;i++) //这里的c[i]与d[i]构成合成后的区间
		cout<<c[i]<<" ";
	cout<<endl;
	for(i=0;i<=temp;i++)
		cout<<d[i]<<" ";
	cout<<endl;
}

//lookup
bool LookUp(int *c,int *d,int begin,int end,int x,int y) //二分查找求满足条件的区间
{
	int middle;
	if(begin == end && begin == 0) { //若最后合并只得到一个数组
		if(c[0]<=x && d[0]>=y)
			return true;
		else return false;
	}
	while(begin<=end)
	{
		middle=(begin+end)/2;
		if(c[middle]<x)
			begin=middle+1;
		else
			end=middle-1;
	}
	cout<<c[end]<<" "<<c[begin]<<endl;
	if(c[end]<=x&&d[end]>=y)
		return true;
	return false;
}

bool projection(int *a,int *b,int n,int x,int y)
{
	Quick(a,b,n);
	int *c=new int [n];
	int *d=new int [n];
	int length;
	unite(a,b,c,d,n, length);
	return LookUp(c,d,0,length-1, x, y);
	delete[]c;
	delete[]d;
}

int main() {
	int n=4;
	int *a=new int [n];//对应 x1, x2, ... , xn
	int *b=new int [n];//对应 y1, y2, ... ,yn
	a[0]=1;
	a[1]=5;
	a[2]=2;
	a[3]=10;
	b[0]=3;
	b[1]=9;
	b[2]=4;
	b[3]=11;
	int x=6;
	int y=10;

/*	int n=3;
	int *a=new int [n];
	int *b=new int [n];
	a[0]=2;
	a[1]=1;
	a[2]=3;
	b[0]=3;
	b[1]=2;
	b[2]=9;	
	int x=1;
	int y=6;*/

	cout<<projection(a,b,n,x, y)<<endl;
	delete []a;
	delete []b;
	return 0;
}

 

 

评论

2 楼 Excalibur 2011-05-04  

和二楼同感，红黑树的变种

1 楼 otupia 2011-05-04  

想起来区间树了，那个算法导论视频里讲的。