What's the most efficient way to test if two ranges overlap?_问答_开发者

Given two inclusive ranges [x1:x2] and [y1:y2], where x1 ≤ x2 and y1 ≤ y2, what i开发者_开发技巧s the most efficient way to test whether there is any overlap of the two ranges?

A simple implementation is as follows:

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

But I expect there are more efficient ways to compute this.

What method would be the most efficient in terms of fewest operations?

What does it mean for the ranges to overlap? It means there exists some number C which is in both ranges, i.e.

x1 <= C <= x2

and

y1 <= C <= y2

To avoid confusion, considering the ranges are: [x1:x2] and [y1:y2]

Now, if we are allowed to assume that the ranges are well-formed (so that x1 <= x2 and y1 <= y2) then it is sufficient to test

x1 <= y2 && y1 <= x2

(StartA <= EndB) and (EndA >= StartB)

Given two ranges [x1,x2], [y1,y2]

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

This can easily warp a normal human brain, so I've found a visual approach to be easier to understand:

What's the most efficient way to test if two ranges overlap?

le Explanation

If two ranges are "too fat" to fit in a slot that is exactly the sum of the width of both, then they overlap.

For ranges [a1, a2] and [b1, b2] this would be:

/**
 * 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!
}

Great answer from Simon, but for me it was easier to think about reverse case.

When do 2 ranges not overlap? They don't overlap when one of them starts after the other one ends:

dont_overlap = x2 < y1 || x1 > y2

Now it easy to express when they do overlap:

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

Subtracting the Minimum of the ends of the ranges from the Maximum of the beginning seems to do the trick. If the result is less than or equal to zero, we have an overlap. This visualizes it well:

What's the most efficient way to test if two ranges overlap?

I suppose the question was about the fastest, not the shortest code. The fastest version have to avoid branches, so we can write something like this:

for simple case:

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

or, for this case:

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

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

Why this works:
The only time the ranges DON'T overlap is when the end of one range is before the beginning of the other. So we want !(x2 < y1 || x1 > y2) which is equivalent to the above.

If you were dealing with, given two ranges [x1:x2] and [y1:y2], natural / anti-natural order ranges at the same time where:

natural order: x1 <= x2 && y1 <= y2 or
anti-natural order: x1 >= x2 && y1 >= y2

then you may want to use this to check:

they are overlapped <=> (y2 - x1) * (x2 - y1) >= 0

where only four operations are involved:

two subtractions
one multiplication
one comparison

If someone is looking for a one-liner which calculates the actual overlap:

int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations

If you want a couple fewer operations, but a couple more variables:

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

You have the most efficient representation already - it's the bare minimum that needs to be checked unless you know for sure that x1 < x2 etc, then use the solutions others have provided.

You should probably note that some compilers will actually optimise this for you - by returning as soon as any of those 4 expressions return true. If one returns true, so will the end result - so the other checks can just be skipped.

Think in the inverse way: how to make the 2 ranges not overlap? Given [x1, x2], then [y1, y2] should be outside [x1, x2], i.e., y1 < y2 < x1 or x2 < y1 < y2 which is equivalent to y2 < x1 or x2 < y1.

Therefore, the condition to make the 2 ranges overlap: not(y2 < x1 or x2 < y1), which is equivalent to y2 >= x1 and x2 >= y1 (same with the accepted answer by Simon).

Given: [x1,x2] [y1,y2] then x1 <= y2 || x2 >= y1 would work always. as

      x1 ... x2
y1 .... y2

if x1 > y2 then they do not overlap or

x1 ... x2
    y1 ... y2

if x2 < y1 they do not overlap.

Nothing new. Just more readable.

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

My case is different. i want check two time ranges overlap. there should not be a unit time overlap. here is Go implementation.

    func CheckRange(as, ae, bs, be int) bool {
    return (as >= be) != (ae > bs)
    }

Test cases

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

you can see there is XOR pattern in boundary comparison

Overlap (X, Y) := if (X1 <= Y1) then (Y1 <= X2) else (X1 <= Y2).

PROOF:

Consider the case when X precedes, or is left aligned with, Y, i.e., X1 <= Y1. Then either Y starts inside, or at the end of, X, i.e. Y1 <= X2; or else Y is away from X. The first condition is overlap; the second, not.

In the complementary case when Y precedes X, the same logic applies to the swapped entities.

So,

Overlap (X, Y) := if (X1 <= Y1) then (Y1 <= X2) else Overlap (Y, X).

But this does not seem quite right. On the recursive call, the first test is redundant, as we already know the relative position of the entities from the first test on the first call. So, we really only need to test for the second condition, which, upon swapping, is (X1 <= Y2). So,

Overlap (X, Y) := if (X1 <= Y1) then (Y1 <= X2) else (X1 <= Y2).

QED.

Implementation in Ada:

   type Range_T is array (1 .. 2) of Integer;

   function Overlap (X, Y: Range_T) return Boolean is
     (if X(1) <= Y(1) then Y(1) <= X(2) else X(1) <= Y(2));

Test program:

with Ada.Text_IO; use Ada.Text_IO;

procedure Main is

   type Range_T is array (1 .. 2) of Integer;

   function Overlap (X, Y: Range_T) return Boolean is
     (if X(1) <= Y(1) then Y(1) <= X(2) else X(1) <= Y(2));

   function Img (X: Range_T) return String is
     (" [" & X(1)'Img & X(2)'Img & " ] ");

   procedure Test (X, Y: Range_T; Expect: Boolean) is
      B: Boolean := Overlap (X, Y);
   begin
      Put_Line
        (Img (X) & " and " & Img (Y) &
         (if B then " overlap .......... "
               else " do not overlap ... ") &
         (if B = Expect then "PASS" else "FAIL"));
   end;
         
begin
   Test ( (1, 2), (2, 3), True);  --  chained
   Test ( (2, 3), (1, 2), True);

   Test ( (4, 9), (5, 7), True);  --  inside
   Test ( (5, 7), (4, 9), True);

   Test ( (1, 5), (3, 7), True);  --  proper overlap
   Test ( (3, 7), (1, 5), True);

   Test ( (1, 2), (3, 4), False);  -- back to back
   Test ( (3, 4), (1, 2), False);

   Test ( (1, 2), (5, 7), False);  -- disjoint
   Test ( (5, 7), (1, 2), False);
end;

Output of above program:

 [ 1 2 ]  and  [ 2 3 ]  overlap .......... PASS
 [ 2 3 ]  and  [ 1 2 ]  overlap .......... PASS
 [ 4 9 ]  and  [ 5 7 ]  overlap .......... PASS
 [ 5 7 ]  and  [ 4 9 ]  overlap .......... PASS
 [ 1 5 ]  and  [ 3 7 ]  overlap .......... PASS
 [ 3 7 ]  and  [ 1 5 ]  overlap .......... PASS
 [ 1 2 ]  and  [ 3 4 ]  do not overlap ... PASS
 [ 3 4 ]  and  [ 1 2 ]  do not overlap ... PASS
 [ 1 2 ]  and  [ 5 7 ]  do not overlap ... PASS
 [ 5 7 ]  and  [ 1 2 ]  do not overlap ... PASS

Here's my version:

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;

Unless you're running some high-performance range-checker on billions of widely-spaced integers, our versions should perform similarly. My point is, this is micro-optimization.