|Ned Batchelder : Blog | Code | Text | Site|
Range overlap in two compares
» Home : Blog : October 2013
I was helping a co-worker with a quick hackathon project (patch-juggler, which will hopefully grow into an interactive rebase GUI), and he had a function to determine whether two ranges overlap.
His code used eight comparisons to check whether the endpoint of one of the ranges was contained within the other range. In Python it would look like this:
I said you could do it in two comparisons rather than eight, but could never remember the trick.
Looking online, I found this great explanation on Stack Overflow. I'll restate it in my own words:
Instead of thinking about how overlapping ranges might relate, consider what conditions have to be true for the ranges not to overlap. It's much simpler: either range1 is entirely less than range2, or range1 is entirely greater than range2.
Since the ranges are ordered (start <= end), range1 less than range2 is true if end1 < start2. Similarly range1 greater than range2 can be determined with end2 < start1.
So we can check for non-overlapping ranges with two compares. Inverting the result tells us whether they overlap:
De Morgan's laws mean that we can change it to this:
Just looking at this final code, it's hard to see the logic. It's even harder to think about it without holding out two fingers on each hand and waving them around to picture overlapping ranges! But with the reasoning about non-overlapping ranges, it makes perfect sense.
This is one of those programming nuggets that makes me happy, I can't explain why.
tagged: coding» 8 reactions