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

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

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

什么方法在最少的操作方面是最有效的？

Answer 1

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

x1 <= C <= x2

和

y1 <= C <= y2

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

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

x1 <= y2 && y1 <= x2

或者

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