测试两个范围是否重叠的最有效方法是什么?

给定两个包含范围[x1:x2]和[y1:y2]，其中x1≤x2和y1≤y2，测试这两个范围是否有重叠的最有效方法是什么?

一个简单的实现如下:

bool testOverlap(int x1, int x2, int y1, int y2) {
  return (x1 >= y1 && x1 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= x1 && y2 <= x2);
}

但是我希望有更有效的方法来计算这个。

就最少的操作而言，哪种方法是最有效的?

当前回答

重叠(X, Y):= if (X1 <= Y1) then (Y1 <= X2) else (X1 <= Y2)。

证明:

考虑X在Y之前或与Y左对齐的情况，即X1 <= Y1。那么Y要么在X内部开始，要么在X的末尾开始，即Y1 <= X2;或者Y远离x，第一个条件是重叠;第二个，不是。

在互补的情况下，Y在X之前，同样的逻辑适用于交换的实体。

So,

重叠(X, Y):= if (X1 <= Y) then (Y1 <= X2) else重叠(Y, X)。

但这似乎并不完全正确。在递归调用中，第一个测试是多余的，因为我们已经从第一个调用的第一个测试中知道了实体的相对位置。因此，我们实际上只需要测试第二个条件，即交换后(X1 <= Y2)。所以,

重叠(X, Y):= if (X1 <= Y1) then (Y1 <= X2) else (X1 <= Y2)。

QED.

Ada的实现:

   type Range_T is array (1 .. 2) of Integer;

   function Overlap (X, Y: Range_T) return Boolean is
     (if X(1) <= Y(1) then Y(1) <= X(2) else X(1) <= Y(2));

测试程序:

with Ada.Text_IO; use Ada.Text_IO;

procedure Main is

   type Range_T is array (1 .. 2) of Integer;

   function Overlap (X, Y: Range_T) return Boolean is
     (if X(1) <= Y(1) then Y(1) <= X(2) else X(1) <= Y(2));

   function Img (X: Range_T) return String is
     (" [" & X(1)'Img & X(2)'Img & " ] ");

   procedure Test (X, Y: Range_T; Expect: Boolean) is
      B: Boolean := Overlap (X, Y);
   begin
      Put_Line
        (Img (X) & " and " & Img (Y) &
         (if B then " overlap .......... "
               else " do not overlap ... ") &
         (if B = Expect then "PASS" else "FAIL"));
   end;
         
begin
   Test ( (1, 2), (2, 3), True);  --  chained
   Test ( (2, 3), (1, 2), True);

   Test ( (4, 9), (5, 7), True);  --  inside
   Test ( (5, 7), (4, 9), True);

   Test ( (1, 5), (3, 7), True);  --  proper overlap
   Test ( (3, 7), (1, 5), True);

   Test ( (1, 2), (3, 4), False);  -- back to back
   Test ( (3, 4), (1, 2), False);

   Test ( (1, 2), (5, 7), False);  -- disjoint
   Test ( (5, 7), (1, 2), False);
end;

以上程序输出:

 [ 1 2 ]  and  [ 2 3 ]  overlap .......... PASS
 [ 2 3 ]  and  [ 1 2 ]  overlap .......... PASS
 [ 4 9 ]  and  [ 5 7 ]  overlap .......... PASS
 [ 5 7 ]  and  [ 4 9 ]  overlap .......... PASS
 [ 1 5 ]  and  [ 3 7 ]  overlap .......... PASS
 [ 3 7 ]  and  [ 1 5 ]  overlap .......... PASS
 [ 1 2 ]  and  [ 3 4 ]  do not overlap ... PASS
 [ 3 4 ]  and  [ 1 2 ]  do not overlap ... PASS
 [ 1 2 ]  and  [ 5 7 ]  do not overlap ... PASS
 [ 5 7 ]  and  [ 1 2 ]  do not overlap ... PASS

2021-12-19 20:00:42

其他回答

return x2 >= y1 && x1 <= y2;

为什么这样做有效: 范围不重叠的唯一情况是当一个范围的结束在另一个范围的开始之前。所以我们想要!(x2 < y1 || x1 > y2)它等价于上面。

2010-07-16 23:12:25

如果有人正在寻找计算实际重叠的一行程序:

int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations

如果你想要少一些操作，但多一些变量:

bool b1 = x2 <= y1;
bool b2 = y2 >= x1;
int overlap = ( !b1 || !b2 ) ? 0 : (y2 >= y1 && b1 ? y1 : y2) - ( x2 <= x1 && b2 ? x1 : x2) + 1; // max 9 operations

2018-06-29 12:04:23

我相信min(upper(A)，upper(B))>=max(lower(A)，lower(B))将是一个很好的解决方案，不仅因为它的简单性，而且因为它超越了两个范围的可扩展性。

2023-01-30 07:25:25

从开始的最大值减去范围末端的最小值似乎可以达到目的。如果结果小于等于零，就有重叠。这很直观:

2016-09-12 14:24:31

值域重叠是什么意思?这意味着存在一个在两个范围内的数C，即。