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

Question

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?

Answer 1

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

x_start <= C <= x_end

and

y_start <= C <= y_end

To avoid confusion, considering the ranges are: [x_start:x_end] and [y_start:y_end]

Now, if we are allowed to assume that the ranges are well-formed (so that x_start <= x_end and y_start <= y_end) then it is sufficient to test

x_start <= y_end && y_start <= x_end