What's the most efficient way to test two integer ranges for overlap?
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
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
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:
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!
}