What's the most efficient way to test if two ranges overlap?
comparison, performance, range
Solution
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
OR
(StartA <= EndB) and (EndA >= StartB)
Problem
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?