A friend of mine called me yesterday about a scheduling application he is working on. His question was so simple, or so it seemed, but it really drove me nuts. Basically he just wanted to find out if two date ranges intersected at all. Simple enough. It was one of those kinds of answers that you immediately start rattling off the solution, but every thing that started to come out of my mouth was failing my mental unit testing. I'll admit it threw me for a loop for a short bit. I was also surprised at the lack of good results from a google search on the subject (so I decieded to post all of this here).
There are various combinations of ranges that kept invalidating each method I would come up with. Some ranges would have a clear intersection where others would have a range that was completely consumed by the other range. Other ranges would barely overlap.
Both my friend and I were sort of shocked that what seemed like such a simple problem would result in us both scratching our heads for a bit. My friend resorted to something that while seemed overly complicated at least was something he knew would work. That was to take the tick value for the dates of each range, create rectanges with those values and then check to see of the rectangles intersected using the built in IntersectsWith method.
Not too bad, it was only really a few lines of code, but such a simple problem deserved a simpler solution. So I drew some date ranges on my witeboard and pick out the most obvious pattern. The ranges seemed to show that if you took the largest of the two start dates and compared it to see if it was before the end date of the opposite range then you'd be able to easily determine if they ranges intersected. Of course if the two start dates were equal then you'd immediately know that the ranges intersected on at least that day so no further checks would be needed. This gave way to the ability to solve this in a single line of code. This sample code returns true if the ranges intersect and uses integers instead of dates to simplify things (First range represented by r1start to r1end and second range represented by r2start to r2end).
private bool intersects(int r1start, int r1end, int r2start, int r2end)
return (r1start == r2start) || (r1start > r2start ? r1start <= r2end : r2start <= r1end);
Ah, much simpler. And it should be for such a simple problem. How else would you have done it?
While my post focused on the algorithim, not the implementation of it, be sure to check out
Jay Bazuzi's much more elegant implementation of this algorithim (see trackback link in comments). Really awesome.