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

Question

假设有两个包含上限和下限值的区间 [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);
}

但我觉得有更有效率的方法可以计算。

在操作最少的情况下，哪种方法是最有效的？

- WilliamKF

---

这可能会对一些人有趣的相关性 - https://dev59.com/Z3PYa4cB1Zd3GeqPiGKE - vsync

Answer 1

什么是范围重叠？这意味着存在某个数C同时存在于两个范围中，即

x1 <= C <= x2

和

y1 <= C <= y2

为避免混淆，请考虑范围为：[x1:x2] 和 [y1:y2] 现在，如果我们可以假设这些范围是良好形式的（因此 x1 <= x2 且 y1 <= y2），那么测试就足够了。

x1 <= y2 && y1 <= x2

或者

(起始时间A小于等于结束时间B)且(结束时间A大于等于起始时间B)

- Simon Nickerson

---

我认为应该是 x1 <= y2 && y1 >= x2，对吗？ - David Beck

@DavidBeck：不，如果y1 > x2，则范围肯定不重叠（例如，考虑[1:2]和[3:4]：y1 = 3，x2 = 2，因此y1 > x2，但没有重叠）。 - Simon Nickerson

如果您能解释推理过程，那么这将是一个更好的答案。 - shoosh

@Vineet Deoraj - 你认为为什么它不起作用？x1 = 1，y1 = 1，x2 = 1，y2 = 1，因此x1 <= y2 && y1 <= x2是真的，因此存在重叠。 - dcp

确定两个日期范围是否重叠的方法是将开始和结束日期转换为时间戳，然后比较它们以查看它们是否相互交叉。如果第一个日期范围的结束日期早于第二个日期范围的开始日期，则它们不重叠。相反，如果第二个日期范围的结束日期早于第一个日期范围的开始日期，则它们也不重叠。否则，它们相互重叠。 - Alex

Answer 2

给定两个区间 [x1,x2] 和 [y1,y2]

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

- KFL

---

@uyuyuy99说：只是不够高效，因为当这个检查每秒钟被执行多次时，调用函数是你想要避免的事情，尽可能自己进行数学计算，保持基本。 - vsync

现代浏览器会内联并优化像 Math.max 这样的函数，对性能应该没有明显影响。 - Ashton Six

@AshtonWar - 很有趣。你有一篇文章解释哪些会被内联和哪些不会吗？ - vsync

@vsync 不，但我相信你可以自己找到相关信息。 - Ashton Six

此外，请注意 min(x2,y2) - max(x1,y1) 可以提供重叠的量，如果您需要的话。 - user1556435

此外，您可以通过以下方式获取交集： start = max(x1,y1); end = start + min(x2,y2) - max(x1,y1)。 感谢user1556435指出了重叠量。 - Rahat Zaman

Answer 3

这个内容可能会扭曲一个普通人的大脑，因此我发现视觉方法更易于理解：

说明

如果两个范围“太宽”以至于无法适合宽度恰好为其总宽度的插槽中，则它们会重叠。

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

- FloatingRock

---

您的图片中所示情况并不全面。例如，如果w2在w1之前开始并在w1结束后才结束，会怎样呢？请问您需要翻译哪种语言呢？ - WilliamKF

@WilliamKF 这个逻辑是正确的。 - FloatingRock

同意，但我认为提供第三张图片可能会有所帮助。 - WilliamKF

@WilliamKF，那么您需要更多的图片，因为有16种不同的组合方式可以放置2个范围... - Peter

如果您使用此方法，请注意，因为总和a2-a1+b2-b1可能会溢出。要修复它，重新排列公式为max（a2，b2）-a2-b2 <min（a1，b1）-a1-b1，这简化为max（a1，b1）<min（a2，b2），可以节省一些算术运算并避免任何可能的溢出（这是AXE-Labs的下面的答案）。在特殊情况下，当您知道b2-b1 = a2-a1时，FloatingRock公式的另一个有用的重新排列是max（a2，b2）-min（a1，b1）-（b2-b1）<a2-a1，其中变成了abs（b1-a1）<a2-a1。 - Paolo Bonzini

Answer 4

虽然Simon的回答很好，但我更容易想到反向情况。

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

dont_overlap = x2 < y1 || x1 > y2

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

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

- Konstantin Milyutin

---

对我来说，更容易理解的表达是：x2 < y1 || y2 < x1 // 在这里我使用“小于”而不是“大于”。 - Park JongBum

Answer 5

从范围结束的最小值中减去开始的最大值似乎是解决方法。如果结果小于或等于零，则存在重叠。以下图片形象地说明了这一点:

- AXE Labs

---

这涵盖了所有情况。 - user3290180

Answer 6

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

为什么这个方法可行：
唯一不重叠的情况是一个范围的结束在另一个范围的开始之前。因此，我们需要!(x2 < y1 || x1 > y2)，这与上面的等式相等。

- BlueRaja - Danny Pflughoeft

---

这不是正确的。因为 x1 <= y1 && x2 >= y2 || x1 >= y1 && x2 <= y2 也应该返回 true。 - Rahat Zaman

@RahatZaman：它在那些情况下也有效。尝试使用一些实际数字进行测试。 - BlueRaja - Danny Pflughoeft

检查 (x1 -> 10, x2 -> 40) (y1 -> 20, y2 -> 30)x2 >= y1 && x1 <= y2 = (40 >= 20) && (10 <= 30) = (true) && (true) = true但是它们明显重叠。 - PRASANNA SARAF

检查 (x1 -> 10, x2 -> 40) (y1 -> 20, y2 -> 30)x2 >= y1 && x1 <= y2 = (40 >= 20) && (10 <= 30) = (true) && (true) = true但是它们明显重叠。 - undefined

@PRASANNASARAF 是的，true 表示它们重叠。 - BlueRaja - Danny Pflughoeft

@PRASANNASARAF 是的，true 表示它们重叠。 - undefined

Answer 7

我假设这个问题是关于最快速的代码，而不是最短的代码。最快速的版本需要避免分支，所以我们可以编写如下代码：

对于简单情况：

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

- ruslik

---

相信你的编译器。假设编译器和CPU架构合理且胜任（即使是在2010年），表达式x1 <= y2 && y1 <= x2[没有任何分支]。事实上，在x86上，简单表达式生成的代码与此答案中的代码基本相同。 - Søren Løvborg

Answer 8

如果你在处理给定的两个区间[x1:x2]和[y1:y2]时，需要同时考虑自然/反自然顺序的范围，其中：

- 自然顺序： x1 <= x2 && y1 <= y2 或 - 反自然顺序： x1 >= x2 && y1 >= y2 那么你可以使用以下方式进行验证：

它们是否重叠<=> (y2 - x1) * (x2 - y1) >= 0 这只涉及到四个操作：

- 两次减法 - 一次乘法 - 一次比较

- Yankuan Zhang

Answer 9

给定： [x1,x2] [y1,y2] 那么x1 <= y2 || x2 >= y1总是有效的。

      x1 ... x2
y1 .... y2

如果 x1 > y2，那么它们不重叠。

x1 ... x2
    y1 ... y2

如果 x2 < y1，则它们不重叠。

- Ioana Bacila

---

这应该是一个“与”操作，而不是“或”操作。 - Stealth Rabbi

Answer 10

如果有人正在寻找一个能够计算实际重叠部分的一行代码：

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

- Victor.dMdB