小编典典

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

all

给定两个包含范围 [x1:x2] 和 [y1:y2],其中x1 ≤ x2y1 ≤ 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);
}

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

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


阅读 73

收藏
2022-04-13

共1个答案

小编典典

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

x1 <= C <= x2

y1 <= C <= y2

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

现在,如果我们可以假设范围是格式正确的(使得 x1 <= x2 和 y1 <= y2),那么测试就足够了

x1 <= y2 && y1 <= x2

或者

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

2022-04-13