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

范围重叠意味着什么？这意味着存在一些在两个范围内的数字 C，即

x1 <= C <= x2

和

y1 <= C <= y2

为避免混淆，考虑范围是：[x1:x2] 和 [y1:y2]

现在，如果我们可以假设范围是格式良好的（使得 x1 <= x2 和 y1 <= y2），那么测试就足够了

x1 <= y2 && y1 <= x2

或者

(StartA <= EndB) 和 (EndA >= StartB)

---

给定两个范围 [x1,x2], [y1,y2]

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)

---

这很容易扭曲正常的人脑，所以我找到了一种更容易理解的视觉方法：

https://i.stack.imgur.com/6iULg.png

解释

如果两个范围“太胖”而无法放入恰好是两者宽度之和的插槽中，则它们会重叠。

对于范围 [a1, a2] 和 [b1, b2]，这将是：

/**
 * we are testing for:
 *     max point - min point < w1 + w2    
 **/
if max(a2, b2) - min(a1, b1) < (a2 - a1) + (b2 - b1) {
  // too fat -- they overlap!
}

---

Simon 的回答很好，但对我来说，考虑反向案例更容易。

2个范围何时不重叠？当其中一个在另一个结束后开始时，它们不会重叠：

dont_overlap = x2 < y1 || x1 > y2

现在很容易表达它们何时重叠：

overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)

---

从开始的最大值中减去范围末端的最小值似乎可以解决问题。如果结果小于或等于零，我们就有重叠。这很好地可视化了它：

https://i.stack.imgur.com/h2Nw2.png

---

我想问题是关于最快的，而不是最短的代码。最快的版本必须避免分支，所以我们可以这样写：

对于简单的情况：

static inline bool check_ov1(int x1, int x2, int y1, int y2){
    // insetead of x1 < y2 && y1 < x2
    return (bool)(((unsigned int)((y1-x2)&(x1-y2))) >> (sizeof(int)*8-1));
};

或者，对于这种情况：

static inline bool check_ov2(int x1, int x2, int y1, int y2){
    // insetead of x1 <= y2 && y1 <= x2
    return (bool)((((unsigned int)((x2-y1)|(y2-x1))) >> (sizeof(int)*8-1))^1);
};

---

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

---

如果您正在处理，给定两个范围 [x1:x2] 和 [y1:y2]，自然/反自然顺序范围同时存在：

自然顺序：x1 <= x2 && y1 <= y2 或

反自然顺序：x1 >= x2 && y1 >= y2

那么你可能想用它来检查：

它们是重叠的 <=> (y2 - x1) * (x2 - y1) >= 0

其中仅涉及四个操作：

两个减法

一乘法

一个比较

---

如果有人正在寻找计算实际重叠的单线：

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

---

以逆向思考：如何使两个范围不重叠？给定 [x1, x2]，则 [y1, y2] 应该在 outside [x1, x2]，即 y1 < y2 < x1 or x2 < y1 < y2 等价于 y2 < x1 or x2 < y1。

因此，使 2 个范围重叠的条件：not(y2 < x1 or x2 < y1)，相当于 y2 >= x1 and x2 >= y1（与 Simon 接受的答案相同）。

---

您已经拥有最有效的表示 - 这是需要检查的最低限度，除非您确定 x1 < x2 等，然后使用其他人提供的解决方案。

您可能应该注意到，一些编译器实际上会为您优化这一点——只要这 4 个表达式中的任何一个返回 true，就会返回。如果一个返回 true，那么最终结果也会如此——因此可以跳过其他检查。

---

我的情况不同。我想检查两个时间范围重叠。不应有单位时间重叠。这是 Go 实现。

    func CheckRange(as, ae, bs, be int) bool {
    return (as >= be) != (ae > bs)
    }

测试用例

if CheckRange(2, 8, 2, 4) != true {
        t.Error("Expected 2,8,2,4 to equal TRUE")
    }

    if CheckRange(2, 8, 2, 4) != true {
        t.Error("Expected 2,8,2,4 to equal TRUE")
    }

    if CheckRange(2, 8, 6, 9) != true {
        t.Error("Expected 2,8,6,9 to equal TRUE")
    }

    if CheckRange(2, 8, 8, 9) != false {
        t.Error("Expected 2,8,8,9 to equal FALSE")
    }

    if CheckRange(2, 8, 4, 6) != true {
        t.Error("Expected 2,8,4,6 to equal TRUE")
    }

    if CheckRange(2, 8, 1, 9) != true {
        t.Error("Expected 2,8,1,9 to equal TRUE")
    }

    if CheckRange(4, 8, 1, 3) != false {
        t.Error("Expected 4,8,1,3 to equal FALSE")
    }

    if CheckRange(4, 8, 1, 4) != false {
        t.Error("Expected 4,8,1,4 to equal FALSE")
    }

    if CheckRange(2, 5, 6, 9) != false {
        t.Error("Expected 2,5,6,9 to equal FALSE")
    }

    if CheckRange(2, 5, 5, 9) != false {
        t.Error("Expected 2,5,5,9 to equal FALSE")
    }

你可以看到边界比较中有异或模式

---

给定：[x1,x2] [y1,y2] 然后 x1 <= y2 || x2 >= y1 将始终有效。作为

      x1 ... x2
y1 .... y2

如果 x1 > y2 则它们不重叠或

x1 ... x2
    y1 ... y2

如果 x2 < y1 它们不重叠。

---

没什么新鲜的。只是更具可读性。

def overlap(event_1, event_2):

    start_time_1 = event_1[0]
    end_time_1 = event_1[1]

    start_time_2 = event_2[0]
    end_time_2 = event_2[1]

    start_late = max(start_time_1, start_time_2)
    end_early = min(end_time_1, end_time_2)


    # The event that starts late should only be after the event ending early.
    if start_late > end_early:
        print("Absoloutly No overlap!")
    else:
        print("Events do overlap!")

---

重叠 (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 的互补情况下，相同的逻辑适用于交换的实体。

所以，

重叠 (X, Y) := 如果 (X1 <= Y1) 然后 (Y1 <= X2) 否则重叠 (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

---

这是我的版本：

int xmin = min(x1,x2)
  , xmax = max(x1,x2)
  , ymin = min(y1,y2)
  , ymax = max(y1,y2);

for (int i = xmin; i < xmax; ++i)
    if (ymin <= i && i <= ymax)
        return true;

return false;

除非您在数十亿个宽间距整数上运行一些高性能范围检查器，否则我们的版本应该执行类似的操作。我的观点是，这是微优化。

---