编程之美2.19区间重合判断

1. 简述

    给定一个源区间[x,y] (y>&＃61;x)和N个无序目标区间[x1,y1][x2,y2][x3,y3]...[xn][yn]&＃xff0c;判断[x,y]是否在目标区间内。

2. 思路

    这个比较简单&＃xff0c;合并目标区间&＃xff0c;判断源区间是否在目标区间内即可。具体过程如下&＃xff1a;
    第一步&＃xff0c;先把目标区间排序。
    第二步&＃xff0c;从第一个区间开始&＃xff0c;遍历首先找到一个[xi,yi]&＃xff0c;使得 x[i]<&＃61; X <&＃61; y[i]&＃xff0c;如果找不到&＃xff0c;说明不在目标区间内&＃xff0c;如果找到了并且yi>&＃61;y&＃xff0c;那么结束工作&＃xff0c;源区间在目标区间内&＃xff0c;如果找到了&＃xff0c;但是yi    第三步&＃xff0c;继续遍历[xi,yi]&＃xff0c;如果xi>y(i-1)&＃xff0c;那么区间断裂&＃xff0c;源区间不在目标区间内&＃xff0c;否则如果yi>&＃61;y&＃xff0c;找到了&＃xff0c;源区间在目标区间内&＃xff0c;否则继续寻找。
    第四步&＃xff0c;如果都遍历结束了&＃xff0c;但是没有发现源区间一定在目标区间内&＃xff0c;说明源区间必然不在目标区间内。

    第一步&＃xff0c;N*LogN&＃xff0c;第二步&＃43;第三步&＃xff0c;N&＃xff0c;第四步&＃xff0c;1。复杂度为O(N LogN)

3. 参考

    编程之美&＃xff0c;2.19&＃xff0c;区间重合判断

#include

#define  N    11 

int Is_Include(int x[], int y[], int X, int Y, int n);

int main()
{
 int  x[N] &＃61; {1,2,7,8,99,143,19,55,33,32,121};
 int  y[N] &＃61; {3,3,20,15,200,202,25,75,35,39,155};

 int X &＃61; 5;
 int Y &＃61; 18;

 int i &＃61; 0;
 int flag &＃61; 0;
 
 printf("The Object Regions Are:\n");
 for (i &＃61; 0; i  {
  if(i &＃61;&＃61; 5)
  {
   printf("\n");
  }

  printf("[%d,%d]\t\t", x[i], y[i]);
 }
 printf("\n");

 flag &＃61; Is_Include(x, y, X, Y, N);
 
 if(flag)
 {
  printf("The Region [%d,%d] Is  In The Object Region.\n", X, Y);
 }
 else
 {
  printf("The Region [%d,%d] Is Not In The Object Region.\n", X, Y);
 }

 return 0;
}

int Is_Include(int x[], int y[], int X, int Y, int n)
{
 int i &＃61; 0;
 int j &＃61; 0;
 int tmpX &＃61; 0;
 int tmpY &＃61; 0;
 int maxY &＃61; y[0];

 for(i &＃61; 1; i  {
  tmpX &＃61; x[i];
  tmpY &＃61; y[i];

  if(y[i] > maxY)
  {
   maxY &＃61; y[i];
  }
  
  j &＃61; i - 1;

  while((j >&＃61; 0) && (x[j] > x[j&＃43;1]))
  {
   x[j&＃43;1] &＃61; x[j];
   y[j&＃43;1] &＃61; y[j];

   j--;
  }

  x[j&＃43;1] &＃61; tmpX;
  y[j&＃43;1] &＃61; tmpY;
 }

 printf("The Object Regions Are:\n");
 for (i &＃61; 0; i  {
  if(i &＃61;&＃61; 5)
  {
   printf("\n");
  }

  printf("[%d,%d]\t\t", x[i], y[i]);
 }
 printf("\n");

 if ((Y > maxY) || (X  {
  return 0;
 }

 if(Y <&＃61; y[0])
 {
  return 1;
 }
 
 for (i &＃61; 0; i  {

  if ( y[i]   {
   continue;
  }
  else
  {
   break;
  }
 
 }

 if (x[i] <&＃61; X && i  {
  if( y[i] > Y )
  {
   return 1;
  }
 }
 else
 {
  return 0;
 }

 tmpY &＃61; y[i];
 tmpX &＃61; x[i];

 for (i &＃61; i &＃43; 1; i  {
  if (x[i] > tmpY)
  {
   return 0;
  }
  if (y[i] > tmpY)
  {
   tmpY &＃61; y[i];
   if (tmpY >&＃61; Y)
   {
    return 1;
   }
  }
 }
 
 
 return 0;
}