首页 > 代码库 > 最大重叠点
最大重叠点
题目：
分析与思考：
这个问题其实不用用b部分提示的那么做，感觉比较复杂。我感觉这种方法不错：首先将n个区间的2n个端点从小到大排序;用一个集合S（顺序统计树，集合中的元素以区间左端点的大小为序）来记录当前发生重叠的区间，初始化S为空。
遍历2n个端点
{
如果该点为某区间左端点
{
将对应区间加入S中；
该区间在S中的（顺序统计）位置，就是该（左端）点对应的重叠个数，如有必要则更新最大重叠个数；
}
如果该点为某区间右端点
{
将对应区间从S中删除；
}
}
这个方法就是求矩形重叠。只不过从判断矩形重叠是否存在后就返回，变为每次插入结点后，就判断结点在区间树的位置，这个位置就是重叠数，然后不断更新最大重叠结点，最后等着2n个端点都遍历完了，就知道其中的最大重叠端点。
程序代码：
归并排序头文件：
struct Array
{
int key;
int index;
};
void MERGE(struct Array B[],int p,int q,int r)
{
int n1=q-p+1,n2=r-q,flag=-1,i,j;//不能为数组A里面的数。
struct Array *L=new struct Array[n1];
struct Array *R=new struct Array[n2];
for (i=1;i<=n1;i++)
{
L[i-1].key=B[p+i-1].key;
L[i-1].index=B[p+i-1].index;
}
for (j=1;j<=n2;j++)
{
R[j-1].key=B[q+j].key;
R[j-1].index=B[q+j].index;
}
L[n1].key=flag;
R[n2].key=flag;
i=0;j=0;
for (int k=p;k<=r;k++)
{
if (L[i].key==flag)
{
B[k].key=R[j].key;
B[k].index=R[j].index;
j++;
}
else if (R[j].key==flag)
{
B[k].key=L[i].key;
B[k].index=L[i].index;
i++;
}
else if (L[i].key<=R[j].key)
{
B[k].key=L[i].key;
B[k].index=L[i].index;
i++;
}
else
{
B[k].key=R[j].key;
B[k].index=R[j].index;
j++;
}
}
}
void MERGE_SORT(struct Array B[],int p,int r)
{
if (p<r)
{
int q=(p+r)/2;
MERGE_SORT(B,p,q);
MERGE_SORT(B,q+1,r);
MERGE(B,p,q,r);
}
}主函数+区间树：
#include <iostream>
#include <conio.h>
#include "MERGE_SORT.h"
using namespace std;
#define BLACK 0
#define RED 1
#define Nil -1
#define LEN sizeof(struct Tree)
#define n 12//区间个数
struct Tree*root=NULL;
struct Tree*nil=NULL;
struct interval
{
int low,high;
};
struct Tree
{
struct Tree*right,*left;
struct Tree*parent;
struct interval Int;
int flag;//1表示已经走过了该区间的左端点，0表示还未到左端点
int Max;
int key;
int color;
int size;
};
int MAX(int a,int b,int c)
{
int temp=a>b?a:b;
return temp>c?temp:c;
}
void LEFT_ROTATE(struct Tree*x)
{//左旋转：分三个步骤①②③来叙述旋转代码的。
struct Tree*y=x->right;//设置y结点。
x->right=y->left;//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。①
if(y->left!=nil)
{
y->left->parent=x;
}
y->parent=x->parent;//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。②
if(x->parent==nil)
{
root=y;
}
else if(x==x->parent->left)
{
x->parent->left=y;
}
else x->parent->right=y;
y->left=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③
x->parent=y;
y->Max=x->Max;
x->Max=MAX(x->Int.high,x->left->Max,x->right->Max);
y->size = x->size; //对附加信息的维护
x->size = x->left->size + x->right->size +1;
}
void RIGHT_ROTATE(struct Tree*x)
{//右旋转：分三个步骤①②③来叙述旋转代码的。
struct Tree*y=x->left;//设置y结点。
x->left=y->right;//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。①
if(y->right!=nil)
{
y->right->parent=x;
}
y->parent=x->parent;//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。②
if(x->parent==nil)
{
root=y;
}
else if(x==x->parent->right)
{
x->parent->right=y;
}
else x->parent->left=y;
y->right=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③
x->parent=y;
y->Max=x->Max;
x->Max=MAX(x->Int.high,x->left->Max,x->right->Max);
y->size = x->size; //对附加信息的维护
x->size = x->left->size + x->right->size +1;
}
void RB_INSERT_FIXUP(struct Tree*z)
{
while (z->parent->color==RED)
{
if (z->parent==z->parent->parent->left)
{
struct Tree*y=z->parent->parent->right;//叔结点
if (y->color==RED)//情况一：叔结点为红色
{//给p1,y,p2着色以保持性质5。并且解决了z的父结点和z都是红色结点问题
z->parent->color=BLACK;
y->color=BLACK;
z->parent->parent->color=RED;
z=z->parent->parent;//把z的祖父结点当成新结点z进入下一次循环
}
else
{
if (z==z->parent->right)//情况二：检查z是否是一个右孩子且叔结点为黑色，前提是p1结点不是叶子结点
{//使用一个左旋让情况2转变为情况3
z=z->parent;
LEFT_ROTATE(z);//由于进入if语句后可知旋转结点不可能是叶子结点，这样就不用判断z是否是叶子结点了。
}
z->parent->color=BLACK;//情况三：是z是一个左孩子且叔结点为黑色，改变z的父和祖父结点颜色并做一次右旋，以保持性质5
z->parent->parent->color=RED;
RIGHT_ROTATE(z->parent->parent);//由于p2可能是叶子结点，所以最好还是用一个if判断
}
}
else//下面else分支类似于上面,注意到else分支的情况2和情况3所做旋转正好是if分支情况的逆。
{
struct Tree*y=z->parent->parent->left;
if (y->color==RED)
{
z->parent->color=BLACK;
y->color=BLACK;
z->parent->parent->color=RED;
z=z->parent->parent;
}
else
{
if (z==z->parent->left)
{
z=z->parent;
RIGHT_ROTATE(z);
}
z->parent->color=BLACK;
z->parent->parent->color=RED;
LEFT_ROTATE(z->parent->parent);
}
}
}
root->color=BLACK;//最后给根结点着为黑色。
}
void RB_INSERT(struct Tree* z)
{
z->key=z->Int.low;
struct Tree*y=nil;
struct Tree*x=root;
while (x!=nil)
{
y=x;
x->size++;
x->Max=MAX(x->Int.high,x->Max,z->Int.high);
if (z->key<x->key)
{
x=x->left;
}
else x=x->right;
}
z->parent=y;
if (y==nil)
{
root=z;
}
else if(z->key<y->key)
{
y->left=z;
}
else y->right=z;
z->left=nil;//给插入结点左右孩子赋值为空。
z->right=nil;
z->color=RED;//给插入结点着为红色。
z->Max=z->Int.high;//+
z->size=1;
z->left->size=0;
z->right->size=0;
RB_INSERT_FIXUP(z);
}
void RB_TRANSPLANT(struct Tree*u,struct Tree*v)
{
if (u->parent==nil)
root=v;
else if(u==u->parent->left)
u->parent->left=v;
else u->parent->right=v;
v->parent=u->parent;
}
//非递归版本的查找二叉查找树的最小值
struct Tree*ITERATIVE_TREE_MINIMUM(struct Tree*x)
{
while (x->left!=nil)
{
x=x->left;
}
return x;
}
//非递归版本的二叉查找树查找函数
struct Tree*ITERATIVE_TREE_SEARCH(struct Tree*x,int k)
{
while (x!=nil&&k!=x->key)
{
if (k<x->key)
{
x=x->left;
}
else x=x->right;
}
return x;
}
void RB_DELETE_FIXUP(struct Tree*x)
{
struct Tree*w=NULL;//w是x的兄弟结点
while (x!=root&&x->color==BLACK)//如果x是黑色并且不是根结点，才进行循环。
{//x是一个具有双重颜色的结点，调整的目的是把x的黑色属性向上移动。
if (x==x->parent->left)
{
w=x->parent->right;
if (w->color==RED)//情况一：x的兄弟结点w是红色的。
{//改变w和x.p的颜色+一次旋转使其变为情况二，三，四。
w->color=BLACK;
x->parent->color=RED;
LEFT_ROTATE(x->parent);
w=x->parent->right;
}
if (w->left->color==BLACK&&w->right->color==BLACK)//情况二：x的兄弟结点w是黑色的，而且w的两个子节点都是黑色。
{
w->color=RED;//从x和w上去掉一重黑色。x还是黑色，而w变为红色。
x=x->parent;//x结点向上移动成为新的待调整结点。
}
else
{
if (w->right->color==BLACK)//情况三：x的兄弟结点w是黑色的，w的左孩子是红色的，w的右孩子是黑色的。
{//交换w和w.left的颜色+旋转使其转变为情况四。
w->left->color=BLACK;
w->color=RED;
RIGHT_ROTATE(w);
w=x->parent->right;
}
w->color=x->parent->color;//以下是情况四：x的兄弟结点w是黑色的，且w的右孩子是红色的。
x->parent->color=BLACK;//置x.p和w.right为黑色+旋转使其去掉x的额外黑色。
w->right->color=BLACK;
LEFT_ROTATE(x->parent);
x=root;//x成为根结点，结束循环。
}
}
else//以下和上面的if分支类似，不做累述。
{
w=x->parent->left;
if (w->color==RED)
{
w->color=BLACK;
x->parent->color=RED;
RIGHT_ROTATE(x->parent);
w=x->parent->left;
}
if (w->left->color==BLACK&&w->right->color==BLACK)
{
w->color=RED;
x=x->parent;
}
else
{
if (w->left->color==BLACK)
{
w->right->color=BLACK;
w->color=RED;
LEFT_ROTATE(w);
w=x->parent->left;
}
w->color=x->parent->color;
x->parent->color=BLACK;
w->left->color=BLACK;
RIGHT_ROTATE(x->parent);
x=root;
}
}
}
x->color=BLACK;
}
void RB_DELETE(struct Tree*z)
{
struct Tree*y=z,*x;//y为待删除或待移动结点
int y_original_color=y->color;//保存y的原始颜色，为做最后的调整做准备。
struct Tree*t=z->parent;
if (z->left==nil)
{
while (t!=nil)
{
t->size--;
t=t->parent;
}
x=z->right;//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
RB_TRANSPLANT(z,z->right);//把以z.right为根的子树替换以z为根的子树。
}
else if (z->right==nil)
{
while (t!=nil)
{
t->size--;
t=t->parent;
}
x=z->left;//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
RB_TRANSPLANT(z,z->left);//把以z.left为根的子树替换以z为根的子树。
}
else
{
y=ITERATIVE_TREE_MINIMUM(z->right);//找到z.right的后继。
struct Tree*t=y->parent;
y->size=z->size-1;//y替换z原来的位置，所以size属性在待删除结点z基础上-1
while (t!=nil)
{
t->size--;
t=t->parent;
}
y_original_color=y->color;//y的新的原始结点被重置。
x=y->right;//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
if (y->parent==z)
{
x->parent=y;//由于z的父结点是要删除的结点，所以不能指向它，于是指向y
}
else
{
RB_TRANSPLANT(y,y->right);//把以y.right为根的子树替换以y为根的子树。
y->right=z->right;
y->right->parent=y;
}
RB_TRANSPLANT(z,y);//把以y为根的子树替换以z为根的子树。
y->left=z->left;
y->left->parent=y;
y->color=z->color;//把已经删除的结点颜色赋值给y，保证了y以上的树结构红黑性质不变。
}
struct Tree*k=x->parent;
while (k!=nil)
{
k->Max=MAX(k->left->Max,k->right->Max,k->Int.high);
k=k->parent;
}
if(y_original_color==BLACK) //y的原始颜色为黑色，说明需要调整红黑颜色。
RB_DELETE_FIXUP(x);
}
bool overlap(struct interval x,struct interval i)
{
if (x.high<i.low||i.high<x.low)
{
return true;//没有重叠
}
else
{
return false;
}
}
struct Tree *INTERVAL_SEARCH(struct Tree *T,struct interval i)
{
struct Tree *x=T;
while (x!=nil&&overlap(x->Int,i))
{
if (x->left!=nil&&x->left->Max>=i.low)
{
x=x->left;
}
else x=x->right;
}
return x;
}
struct Tree*OS_SELECT(struct Tree*x,int i)//查找顺序统计树给定秩的元素
{
int r=x->left->size+1;
if (i==r)
{
return x;
}
else if (i<r)
{
return OS_SELECT(x->left,i);
}
else return OS_SELECT(x->right,i-r);
}
int ITERATIVE_OS_RANK(struct Tree*T,struct Tree*x)//确定顺序统计树的秩
{
int r=x->left->size+1;
struct Tree*y=x;
while (y!=root)
{
if (y==y->parent->right)
{
r=r+y->parent->left->size+1;
}
y=y->parent;
}
return r;
}
struct Tree* FIND_POM(struct Tree A[],struct Array B[])
{//判断n个矩阵是否重叠，运行时间为O(nlgn)
int i=1,t=0,M=0;
struct Tree*MAX=NULL;
while (i!=2*n)
{
if (A[B[i].index].flag==0)//0代表矩形Ri的纵坐标的还未进入扫描线。
{
struct Tree*z=new struct Tree[LEN];
z->key=A[B[i].index].Int.low;
z->Int.low=A[B[i].index].Int.low;
z->Int.high=A[B[i].index].Int.high;
A[B[i].index].flag=1;
RB_INSERT(z);//将这个矩形插入进区间树
t=ITERATIVE_OS_RANK(root,z);
if (t>M)
{
M=t;
MAX=z;
}
}
else//否则，矩形Ri的纵坐标进入过扫描线了，那么遇到的横坐标(B[i].key代表横坐标)必然是Ri的高端点。
{
if (i==2*n-1||A[B[i+1].index].Int.low!=A[B[i].index].Int.high)
{
struct Tree*z=ITERATIVE_TREE_SEARCH(root,A[B[i].index].Int.low);//先找到区间树中的这个结点。
RB_DELETE(z);//从区间树中删除这个矩形。
}
}
i++;
}
return MAX;
}
void init(struct Tree A[],struct Array B[])
{//区间树初始化。
nil=new struct Tree[LEN];//设置叶子结点
nil->key=Nil;nil->color=BLACK;
root=nil;
int i=0;
struct Tree*z=new struct Tree[LEN];//设置根结点。
z->key=A[B[i].index].Int.low;
z->Int.low=A[B[i].index].Int.low;
z->Int.high=A[B[i].index].Int.high;
RB_INSERT(z);
root=z;
A[B[i].index].flag=1;
}
void main()
{
struct Tree A[n]={0};
struct Array B[2*n]={0};
for (int i=0,j=0;i<n,j<2*n;i++,j+=2)
{
cout<<"请输入第"<<i<<"个矩阵的数据："<<endl;
cout<<" y的低端点=";cin>>A[i].Int.low;
cout<<" y的高端点=";cin>>A[i].Int.high;
B[j].key=A[i].Int.low;
B[j+1].key=A[i].Int.high;
B[j].index=i;
B[j+1].index=i;
}
MERGE_SORT(B,0,2*n-1);//归并排序，时间为O(nlgn)
init(A,B);
cout<<FIND_POM(A,B)->key<<endl;
}总结：
和14.3-7求重叠矩形类似，换汤不换药。由于要循环遍历这2n个端点，并且每次遍历时要进行插入删除操作顺便记录最大值，所以运行时间是O(nlgn)，而《教师手册》说FIND_POM函数只需要O(1)时间，这是因为没有算上插入的时间。如果要查找这n个区间的最大重叠点肯定要进行插入组成一棵树，总的时间不会少于O(nlgn)的，而本文的FIND_POM操作把组建这棵树的时间也算在内了。总得来说，两种方法差不多，只是本文的方法比较简单易懂罢了。参考资料：这里有相关问题的讨论
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。