给定两个包含范围[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);
}

但是我希望有更有效的方法来计算这个。

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


当前回答

值域重叠是什么意思?这意味着存在一个在两个范围内的数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)

其他回答

考虑到: (x1, x2) (y1, y2) 那么x1 <= y2 || x2 >= y1总是成立的。 作为

      x1 ... x2
y1 .... y2

如果是x1 > y2,那么它们不重叠 或

x1 ... x2
    y1 ... y2

如果x2 < y1,它们不重叠。

我的情况不同。我要检查两个时间范围是否重叠。不应该有单位时间的重叠。这里是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")
    }

你可以在边界比较中看到异或模式

这很容易扭曲正常人的大脑,所以我找到了一个更容易理解的视觉方法:

勒解释

如果两个范围“太胖”,无法放入正好是两者宽度之和的槽中,那么它们就会重叠。

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

你已经有了最有效的表示——这是需要检查的最小值,除非你确定x1 < x2等,然后使用其他人提供的解决方案。

你可能应该注意到,一些编译器实际上会为你优化它——只要这4个表达式中的任何一个返回true就返回。如果其中一个返回true,那么最终结果也会返回true——因此可以跳过其他检查。

如果有人正在寻找计算实际重叠的一行程序:

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