给定两个包含范围[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);
}
但是我希望有更有效的方法来计算这个。
就最少的操作而言，哪种方法是最有效的?
当前回答
如果有人正在寻找计算实际重叠的一行程序:
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
其他回答
我的情况不同。我要检查两个时间范围是否重叠。不应该有单位时间的重叠。这里是Go的实现。
func CheckRange(as, ae, bs, be int) bool {
return (as >= be) != (ae > bs)
}
测试用例
if CheckRange(2, 8, 2, 4) != true {
t.Error("Expected 2,8,2,4 to equal TRUE")
}
if CheckRange(2, 8, 2, 4) != true {
t.Error("Expected 2,8,2,4 to equal TRUE")
}
if CheckRange(2, 8, 6, 9) != true {
t.Error("Expected 2,8,6,9 to equal TRUE")
}
if CheckRange(2, 8, 8, 9) != false {
t.Error("Expected 2,8,8,9 to equal FALSE")
}
if CheckRange(2, 8, 4, 6) != true {
t.Error("Expected 2,8,4,6 to equal TRUE")
}
if CheckRange(2, 8, 1, 9) != true {
t.Error("Expected 2,8,1,9 to equal TRUE")
}
if CheckRange(4, 8, 1, 3) != false {
t.Error("Expected 4,8,1,3 to equal FALSE")
}
if CheckRange(4, 8, 1, 4) != false {
t.Error("Expected 4,8,1,4 to equal FALSE")
}
if CheckRange(2, 5, 6, 9) != false {
t.Error("Expected 2,5,6,9 to equal FALSE")
}
if CheckRange(2, 5, 5, 9) != false {
t.Error("Expected 2,5,5,9 to equal FALSE")
}
你可以在边界比较中看到异或模式
西蒙的回答很好，但对我来说，相反的情况更容易思考。
什么时候两个范围不重叠?当其中一个开始后另一个结束时，它们不会重叠:
dont_overlap = x2 < y1 || x1 > y2
当它们重叠时，很容易表示:
overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)
如果有人正在寻找计算实际重叠的一行程序:
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
以下是我的看法:
int xmin = min(x1,x2)
, xmax = max(x1,x2)
, ymin = min(y1,y2)
, ymax = max(y1,y2);
for (int i = xmin; i < xmax; ++i)
if (ymin <= i && i <= ymax)
return true;
return false;
除非您正在对数十亿个宽间距整数运行一些高性能的范围检查器，否则我们的版本应该执行类似的操作。我的观点是，这是微观优化。
什么新东西。只是可读性更强。
def overlap(event_1, event_2):
start_time_1 = event_1[0]
end_time_1 = event_1[1]
start_time_2 = event_2[0]
end_time_2 = event_2[1]
start_late = max(start_time_1, start_time_2)
end_early = min(end_time_1, end_time_2)
# The event that starts late should only be after the event ending early.
if start_late > end_early:
print("Absoloutly No overlap!")
else:
print("Events do overlap!")
