Alex Rivera | Logout

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

Asked 2010-07-16T23:08:48.060
436

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?

Edit
Report

1 Answer

24
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, x2 < y1 || x1 > y2. What we want is the opposite of that:

!(x2 < y1 || x1 > y2)

which by Demorgan's Laws is equivalent to the first expression.

answered 2010-07-16T23:12:25.527

Your Answer