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

小开

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

小开

最佳答案

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

x1 <= C <= x2

而且

y1 <= C <= y2

为了避免混淆，考虑范围为: [x1:x2] and [y1:y2]

现在，如果我们允许假设范围是良好形成的(因此x1 <= x2和y1 <= y2)，那么就足以进行测试

x1 <= y2 && y1 <= x2

或

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

小开

你已经有了最有效的表示法-这是需要检查的最小值除非你确定x1 <X2等，然后使用别人提供的解决方案。

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

小开

以下是我的看法:

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;

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

小开

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

对于简单的例子:

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);
};

小开

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

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

小开

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

重叠疯狂

勒解释

如果两个范围是“太胖了”，以适合一个插槽，正好是两者宽度的和，那么它们重叠。

对于[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!
}

小开

西蒙的回答很好，但对我来说，相反的情况更容易思考。

什么时候两个范围不重叠?当其中一个开始后另一个结束时，它们不会重叠:

dont_overlap = x2 < y1 || x1 > y2

当它们重叠时，很容易表示:

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

小开

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

小开

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

自然顺序:x1 <= x2 && y1 <= y2或
反自然顺序:x1 >= x2 && y1 >= y2

然后你可能想用这个来检查:

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

其中只涉及四个操作:

2倍
一个乘法
一个比较

小开

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

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]应该是外 [x1, x2]，即y1 < y2 < x1 or x2 < y1 < y2，它等价于y2 < x1 or x2 < y1。

因此，使两个范围重叠的条件是:not(y2 < x1 or x2 < y1)，它等价于y2 >= x1 and x2 >= y1(与Simon接受的答案相同)。

小开

我的情况不同。我要检查两个时间范围是否重叠。不应该有单位时间的重叠。这里是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")
}

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

小开

< p >给定: [x1,x2] [y1,y2] 那么x1 <= y2 || x2 >= y1将始终工作。 < / p >

      x1 ... x2
y1 .... y2

如果x1 > y2则它们不重叠或者< / p >

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):= if (X1 <= Y1) 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