来源：蜘蛛抓取(WebSpider)
时间：2017-02-09 08:15
标签：
判断区间是否重叠
确定一组矩形是否有两个重叠的算法
注：更正一下：在英文原版书中，“请给出一个能在O(nlgn)”时间里确定一组矩形中是否有两个重叠的算法。”而不是中文版的 O(lgn).因为这个问题里涉及的排序算法就至少是O(nlgn)。
基本思想：
经提示用以矩形横坐标x为轴作为扫描线，从所有矩形x最小值到矩阵x最大值，当然在这之前要对所有矩形的横坐标x做一个排序，我用的是归并排序。
扫描过程如图所示的三个矩形中，从x1开始扫描，遇到矩形Gi的左x坐标，将Gi的纵坐标y的低端点和高端点组成的区间插入区间树后，判断矩阵Gi与区间树中已有的区间是否重叠，若重叠则返回真以证明重叠矩形存在，若没有重叠，则继续扫描x。如果遇到矩形Gi的右x坐标,说明再往后扫描就不会与Gi矩形重叠，所以把Gi删除。如此循环往复。图中所给三个矩形G1,G2,G3.应该从x1扫描到x2程序就自动终止证明重叠矩形存在，不会扫描到G3。
总体来看：①先做归并排序(时间O(nlgn))
②再做区间树的插入删除以及重叠操作(O(nlgn)).
代码如下：
"MERGE_SORT.h"头文件
struct Array
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].
L[i-1].index=B[p+i-1].
for (j=1;j<=n2;j++)
R[j-1].key=B[q+j].
R[j-1].index=B[q+j].
L[n1].key=
R[n2].key=
for (int k=p;k<=r;k++)
if (L[i].key==flag)
B[k].key=R[j].
B[k].index=R[j].
else if (R[j].key==flag)
B[k].key=L[i].
B[k].index=L[i].
else if (L[i].key<=R[j].key)
B[k].key=L[i].
B[k].index=L[i].
B[k].key=R[j].
B[k].index=R[j].
void MERGE_SORT(struct Array B[],int p,int r)
int q=(p+r)/2;
MERGE_SORT(B,p,q);
MERGE_SORT(B,q+1,r);
MERGE(B,p,q,r);
}主函数+区间树
#include "MERGE_SORT.h"
#define BLACK 0
#define RED 1
#define Nil -1
#define LEN sizeof(struct Tree)
#define n 4//矩形的个数
struct Tree*root=NULL;
struct Tree*nil=NULL;
struct interval
 int low,
struct Rectangular
  struct interval x,y;
struct Tree
 struct Tree*right,*
 struct Tree*
 struct interval I
 int M
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->//设置y结点。
 x->right=y->//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。①
 if(y->left!=nil)
       y->left->parent=x;
 y->parent=x->//本行代码以及下面的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->M
 x->Max=MAX(x->Int.high,x->left->Max,x->right->Max);
void RIGHT_ROTATE(struct Tree*x)
{//右旋转：分三个步骤①②③来叙述旋转代码的。
 struct Tree*y=x->//设置y结点。
 x->left=y->//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。①
 if(y->right!=nil)
  y->right->parent=x;
 y->parent=x->//本行代码以及下面的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->M
 x->Max=MAX(x->Int.high,x->left->Max,x->right->Max);
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->//叔结点
     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->//把z的祖父结点当成新结点z进入下一次循环
     }
     else
     {
      if (z==z->parent->right)//情况二：检查z是否是一个右孩子且叔结点为黑色，前提是p1结点不是叶子结点
      {//使用一个左旋让情况2转变为情况3
       z=z->
       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->
     if (y->color==RED)
     {
      z->parent->color=BLACK;
      y->color=BLACK;
      z->parent->parent->color=RED;
      z=z->parent->
     }
     else
     {
      if (z==z->parent->left)
      {
       z=z->
       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.
 struct Tree*y=
 struct Tree*x=
 while (x!=nil)
  y=x;
  x->Max=MAX(x->Int.high,x->Max,z->Int.high);
  if (z->keykey)
  {
   x=x->
  }
  else x=x->
 z->parent=y;
 if (y==nil)
  root=z;
 else if(z->keykey)
  y->left=z;
 else y->right=z;
 z->left=//给插入结点左右孩子赋值为空。
 z->right=
 z->color=RED;//给插入结点着为红色。
 z->Max=z->Int.//+
 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->
//非递归版本的查找二叉查找树的最小值
struct Tree*ITERATIVE_TREE_MINIMUM(struct Tree*x)
 while (x->left!=nil)
  x=x->
//非递归版本的二叉查找树查找函数
struct Tree*ITERATIVE_TREE_SEARCH(struct Tree*x,int k)
 while (x!=nil&&k!=x->key)
  if (kkey)
  {
   x=x->
  }
  else x=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->
    if (w->color==RED)//情况一：x的兄弟结点w是红色的。
    {//改变w和x.p的颜色+一次旋转使其变为情况二，三，四。
     w->color=BLACK;
     x->parent->color=RED;
     LEFT_ROTATE(x->parent);
     w=x->parent->
    }
    if (w->left->color==BLACK&&w->right->color==BLACK)//情况二：x的兄弟结点w是黑色的，而且w的两个子节点都是黑色。
    {
     w->color=RED;//从x和w上去掉一重黑色。x还是黑色，而w变为红色。
     x=x->//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->
     }
     w->color=x->parent->//以下是情况四：x的兄弟结点w是黑色的，且w的右孩子是红色的。
     x->parent->color=BLACK;//置x.p和w.right为黑色+旋转使其去掉x的额外黑色。
     w->right->color=BLACK;
     LEFT_ROTATE(x->parent);
     x=//x成为根结点，结束循环。
    }
   }
   else//以下和上面的if分支类似，不做累述。
   {
             w=x->parent->
    if (w->color==RED)
    {
     w->color=BLACK;
     x->parent->color=RED;
     RIGHT_ROTATE(x->parent);
     w=x->parent->
    }
    if (w->left->color==BLACK&&w->right->color==BLACK)
    {
     w->color=RED;
     x=x->
    }
    else
    {
     if (w->left->color==BLACK)
     {
      w->right->color=BLACK;
      w->color=RED;
      LEFT_ROTATE(w);
      w=x->parent->
     }
     w->color=x->parent->
     x->parent->color=BLACK;
     w->left->color=BLACK;
     RIGHT_ROTATE(x->parent);
     x=
    }
   }
     }
  x->color=BLACK;
void RB_DELETE(struct Tree*z)
    struct Tree*y=z,*x;//y为待删除或待移动结点
 int y_original_color=y->//保存y的原始颜色，为做最后的调整做准备。
 if (z->left==nil)
  x=z->//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
  RB_TRANSPLANT(z,z->right);//把以z.right为根的子树替换以z为根的子树。
 else if (z->right==nil)
  x=z->//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上
  RB_TRANSPLANT(z,z->left);//把以z.left为根的子树替换以z为根的子树。
 else
  y=ITERATIVE_TREE_MINIMUM(z->right);//找到z.right的后继。
        y_original_color=y->//y的新的原始结点被重置。
  x=y->//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->
   y->right->parent=y;
  }
  RB_TRANSPLANT(z,y);//把以y为根的子树替换以z为根的子树。
  y->left=z->
  y->left->parent=y;
  y->color=z->//把已经删除的结点颜色赋值给y，保证了y以上的树结构红黑性质不变。
 struct Tree*k=x->
 while (k!=nil)
  k->Max=MAX(k->left->Max,k->right->Max,k->Int.high);
  k=k->
  }
 if(y_original_color==BLACK) //y的原始颜色为黑色，说明需要调整红黑颜色。
  RB_DELETE_FIXUP(x);
bool overlap(struct interval x,struct interval i)
 if (x.high<i.low||i.highInt,i))
   {
    if (x->left!=nil&&x->left->Max>=i.low)
    {
     x=x->
    }
    else x=x->
   }
  
bool Rectangle_overlap(struct Rectangular A[],struct Array B[])
{//判断n个矩阵是否重叠，运行时间为O(nlgn)
 int i=1;
 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].y.
   z->Int.low=A[B[i].index].y.
   z->Int.high=A[B[i].index].y.
   A[B[i].index].flag=1;
   if (root!=z&&INTERVAL_SEARCH(root,z->Int)!=nil)
   {//如果矩形重叠存在，那么直接返回。
    
   }
   RB_INSERT(z);//将这个矩形插入进区间树
  }
  else//否则，矩形Ri的纵坐标进入过扫描线了，那么遇到的横坐标(B[i].key代表横坐标)必然是Ri的高端点。
  {
   if (i==2*n-1||A[B[i+1].index].y.low!=A[B[i].index].y.high)
   {
    struct Tree*z=ITERATIVE_TREE_SEARCH(root,A[B[i].index].y.low);//先找到区间树中的这个结点。
       RB_DELETE(z);//从区间树中删除这个矩形。
   }
  }
  i++;
void init(struct Rectangular A[],struct Array B[])
{//区间树初始化。
 nil=new struct Tree[LEN];//设置叶子结点
 nil->key=Nnil->color=BLACK;
 root=
 int i=0;
 struct Tree*z=new struct Tree[LEN];//设置根结点。
 z->key=A[B[i].index].y.
 z->Int.low=A[B[i].index].y.
    z->Int.high=A[B[i].index].y.
 RB_INSERT(z);
 root=z;
 A[B[i].index].flag=1;
int char_int()
 int i=0,s=0,t=1;
 char ch1[n]={0};
 while (ch!=' ')
  if (ch=='#')
  {
   while (i)
   {
    cout<<"\b";
    ch1[i]=' ';
    i--;
   }
  }
  ch=getch();
  cout<<
  ch1[i++]=
 cout <1)
  s+=(ch1[i---2]-'0')*t;
  t*=10;
  cout << "\b";
void main()
 struct Rectangular 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<<"个矩阵的数据：(按#号键重新输入，按空格键结束输入)"<<
  cout<<"x的左端点=";cout<<(A[i].x.low=char_int());
  cout<<" x的右端点=";cout<<(A[i].x.high=char_int());
  cout<<" y的低端点=";cout<<(A[i].y.low=char_int());
  cout<<" y的高端点=";cout<<(A[i].y.high=char_int())<<
  B[j].key=A[i].x.
  B[j+1].key=A[i].x.
  B[j].index=i;
  B[j+1].index=i;
 MERGE_SORT(B,0,2*n-1);//归并排序，时间为O(nlgn)
 init(A,B);
 if(Rectangle_overlap(A,B))
  cout<<"重叠矩阵存在！"<<
 else cout<<"重叠矩阵不存在"<<
最后测试时注意，和通常输入数据不太一样的是按空格结束输入并且按#号重新输入！
样例输入：

(window.slotbydup=window.slotbydup || []).push({
id: '2467140',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467141',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467142',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467143',
container: s,
size: '1000,90',
display: 'inlay-fix'
(window.slotbydup=window.slotbydup || []).push({
id: '2467148',
container: s,
size: '1000,90',
display: 'inlay-fix'2003年11月 专题开发/技术/项目大版内专家分月排行榜第二2003年2月 专题开发/技术/项目大版内专家分月排行榜第二
本帖子已过去太久远了，不再提供回复功能。* PHP计算两个时间段是否有交集（边界重叠不算）
* @param string $beginTime1 开始时间1
* @param string $endTime1 结束时间1
* @param string $beginTime2 开始时间2
* @param string $endTime2 结束时间2
* @return bool
function is_time_cross($beginTime1 = '', $endTime1 = '', $beginTime2 = '', $endTime2 = ''){
$status = $beginTime2 - $beginTime1;
if ($status & 0){
$status2 = $beginTime2 - $endTime1;
if ($status2 & 0){
return false;
}elseif ($status2 & 0){
return true;
return false;
}elseif($status & 0){
$status2 = $endTime2 - $beginTime1;
if ($status2 & 0){
return true;
}else if ($status2 & 0){
return false;
return false;
$status2 = $endTime2 - $beginTime1;
if ($status2 == 0){
return false;
return true;
阅读(...) 评论()
