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

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

这很容易扭曲正常的人脑，因此我发现一种视觉方法更容易理解：

解释

如果两个范围“太胖”以致不能恰好是两个宽度的总和，则它们会重叠。

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

}