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

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

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


当前回答

什么新东西。只是可读性更强。

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!")

其他回答

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

反过来思考:如何使这两个范围不重叠?给定[x1, x2],则[y1, y2]应在[x1, x2]之外,即y1 < y2 < x1或x2 < y1 < y2,这等价于y2 < x1或x2 < y1。

因此,使两个范围重叠的条件是:不(y2 < x1或x2 < y1),这相当于y2 >= x1和x2 >= y1(与Simon接受的答案相同)。

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

对于简单的例子:

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);
};

从开始的最大值减去范围末端的最小值似乎可以达到目的。如果结果小于等于零,就有重叠。这很直观: