测试两个范围是否重叠的最有效方法是什么? [英] What's the most efficient way to test if two ranges overlap?

问题描述

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

Given two inclusive ranges [x1:x2] and [y1:y2], where x1 ≤ x2 and y1 ≤ y2, what is the most efficient way to test whether there is any overlap of the two ranges?

一个简单的实现如下:

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

但我希望有更有效的方法来计算.

But I expect there are more efficient ways to compute this.

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

What method would be the most efficient in terms of fewest operations?

推荐答案

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

What does it mean for the ranges to overlap? It means there exists some number C which is in both ranges, i.e.

x1 <= C <= x2

和

y1 <= C <= y2

为避免混淆，请考虑以下范围:[x1:x2] 和 [y1:y2]

To avoid confusion, considering the ranges are: [x1:x2] and [y1:y2]

现在，如果允许我们假设范围是格式良好的(因此 x1 <= x2 和 y1 <= y2)，那么测试就足够了

Now, if we are allowed to assume that the ranges are well-formed (so that x1 <= x2 and y1 <= y2) then it is sufficient to test

x1 <= y2 && y1 <= x2

或

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

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

这篇关于测试两个范围是否重叠的最有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！