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

user_115751 0
Viewed 142680

Given two inclusive ranges [x1:x2] and [y1:y2], where x1 ≤ x2 and y1 ≤ y2, what is 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?

range comparison performance
16 Answers

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
user_19122490

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).

user_8910460

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

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

user_8840520

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.

user_115327840

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
user_19910460
Related