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

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 <= y2 && y1 <= x2

Answer 2

给定两个范围[x1,x2],[y1,y2]

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)

Answer 3

这很容易扭曲正常的人脑,所以我发现了一种更容易理解的视觉方法:

le解释

如果两个范围"太胖"以适合恰好是两者宽度之和的槽,则它们重叠.

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

Answer 4

西蒙很好的回答,但对我来说,考虑反向案例更容易.

2个范围何时不重叠？当其中一个在另一个结束后开始时,它们不重叠:

dont_overlap = x2 < y1 || x1 > y2

现在,当它们重叠时很容易表达:

overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)

Answer 5

从最大值开始减去范围的最小值似乎可以解决问题.如果结果小于或等于零,则我们有重叠.这可视化很好:

Answer 6

我想这个问题是关于最快的,而不是最短的代码.最快的版本必须避免分支,所以我们可以写这样的东西:

对于简单的情况:

static inline bool check_ov1(int x1, int x2, int y1, int y2){
    // insetead of x1 < y2 && y1 < x2
    return (bool)(((unsigned int)((y1-x2)&(x1-y2))) >> (sizeof(int)*8-1));
};

或者,对于这种情况:

static inline bool check_ov2(int x1, int x2, int y1, int y2){
    // insetead of x1 <= y2 && y1 <= x2
    return (bool)((((unsigned int)((x2-y1)|(y2-x1))) >> (sizeof(int)*8-1))^1);
};

Answer 7

return x2 >= y1 && x1 <= y2;

Answer 8

如果您正在处理，同时给定两个范围[x1:x2]和[y1:y2]自然/反自然顺序范围，其中：

• 自然顺序：x1 <= x2 && y1 <= y2或
• 反自然秩序： x1 >= x2 && y1 >= y2

那么你可能想用它来检查：

它们是重叠的<=> (y2 - x1) * (x2 - y1) >= 0

其中只涉及四个操作：

• 两次减法
• 一次乘法
• 一比较