/*
* 区间重合判断
* 比如,给出待判断区间[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;
}
