给定两个包含范围[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);
}
但是我希望有更有效的方法来计算这个。
就最少的操作而言，哪种方法是最有效的?
当前回答
西蒙的回答很好，但对我来说，相反的情况更容易思考。
什么时候两个范围不重叠?当其中一个开始后另一个结束时，它们不会重叠:
dont_overlap = x2 < y1 || x1 > y2
当它们重叠时，很容易表示:
overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)
其他回答
return x2 >= y1 && x1 <= y2;
为什么这样做有效: 范围不重叠的唯一情况是当一个范围的结束在另一个范围的开始之前。所以我们想要!(x2 < y1 || x1 > y2)它等价于上面。
值域重叠是什么意思?这意味着存在一个在两个范围内的数C，即。
x1 <= C <= x2
and
y1 <= C <= y2
为了避免混淆，考虑范围为: [x1:x2]和[y1:y2]
现在，如果我们可以假设范围是构造良好的(因此x1 <= x2和y1 <= y2)，那么就足以进行测试
x1 <= y2 && y1 <= x2
OR
(StartA <= EndB)和(EndA >= StartB)
如果有人正在寻找计算实际重叠的一行程序:
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
考虑到: (x1, x2) (y1, y2) 那么x1 <= y2 || x2 >= y1总是成立的。 作为
x1 ... x2
y1 .... y2
如果是x1 > y2，那么它们不重叠 或
x1 ... x2
y1 ... y2
如果x2 < y1，它们不重叠。
从开始的最大值减去范围末端的最小值似乎可以达到目的。如果结果小于等于零，就有重叠。这很直观:
