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

Solution 1:

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

To avoid confusion, considering the ranges are: [x1:x2] and [y1: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

(StartA <= EndB) and (EndA >= StartB)

Solution 2:

Given two ranges [x1,x2], [y1,y2]

def is_overlapping(x1,x2,y1,y2):
    return max(x1,y1) <= min(x2,y2)

Solution 3:

This can easily warp a normal human brain, so I've found a visual approach to be easier to understand:

overlap madness

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!
}

Solution 4:

Great answer from Simon, but for me it was easier to think about reverse case.

When do 2 ranges not overlap? They don't overlap when one of them starts after the other one ends:

dont_overlap = x2 < y1 || x1 > y2

Now it easy to express when they do overlap:

overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)