测试两个范围是否重叠的最有效方法是什么?

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

2016-03-02 17:36:28

其他回答

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

勒解释

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

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

2014-08-18 17:50:02

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

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

2021-07-20 02:50:45

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

对于简单的例子:

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

2010-07-19 09:06:32

值域重叠是什么意思?这意味着存在一个在两个范围内的数C，即。