Intersection of Date Ranges

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?

Note: 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.

Posted on Thursday, August 19, 2004 8:51 AM

Feedback

# Comparing ranges - jaybaz [MS] WebLog

8/19/2004 12:52 PM

# re: Intersection of Date Ranges - Martin

i would compute the section of r1 and r2 as the range from sstart = max(r1start, r2start) to send = min (r1end, r2end) and then check whether that section range is not empty = sstart <= send.

private bool intersects (int r1start, int r1end, int r2start, int r2end) {
int sstart = r1start > r2start ? r1start : r2start; // max of starts
int send = r1end < r2end ? r1end : r2end; // min of ends
return sstart <= send; // section not empty ?
}

i would prefer this solution, cause i believe its easier to see that all cases are covered.

performance should be the same, cause both need three compares.

8/19/2004 1:58 PM

# re: Intersection of Date Ranges - Ryan Farley

Nice Martin. That does add some clarity to the code and makes it easier to read. Thanks.

8/19/2004 2:01 PM

# Comparing ranges - jaybaz [MS] WebLog

8/19/2004 5:14 PM

# re: Intersection of Date Ranges - J.M

I'm not sure about performanc on this one, but it might be more clear
private bool intersects(int r1start, int r1end, intr2start, int r2end)
{
int sstart = Math.Max(r1start, r2start);
int send = Math.Min(r1end, r2end);
return sstart <= send;
}

I'm not sure that it's as fast because of the calls to Math.Min/Max -- not sure whether that gets inlined or not.

It might be more clear for people who are not used to "parsing" the ?: operator.

8/19/2004 3:16 PM

# re: Intersection of Date Ranges - Ryan Farley

Not bad J.M., but I'd probably stay away from the Math classes for that (I'm not sure either if they get inlined and there are equally as simple ways to do it anyway)

Here's a cool way to do it, this was posted in the comments on jaybaz's blog:

[quote from Dithermaster]
A friend approached me years ago about finding if a time range overlaps. There are just so many cases. However, (and the "ah ha!" moment), it's *much* easier to find out of they DON'T overlap, and negate that.

In other words (in C):

overlap = ! ( (end2 < start1) || (start2 > end1) );
[/quote]

Not too bad. Very nice.

8/19/2004 3:23 PM

# re: Intersection of Date Ranges - Ryan Jameson

The cool thing about the "Dithermaster method" above is that it can easily be implemented in a T-Sql "Select" without having to resort to an "IF-ELSE" in a UDF:

--------------------------------------------------------------------------------------
Declare @startdate DateTime Set @startdate = '1/1/2004'
Declare @enddate DateTime Set @enddate = '12/31/2004'

Select
*
From
[Plan]
Where
(NOT((PlanEnd < @startdate) or (PlanStart > @enddate)))
---------------------------------------------------------------------------------------

8/21/2004 11:13 AM

# re: Intersection of Date Ranges - Scott

That is just awesome. I had been looking for a way to solve this problem for a couple of months now. Finally, I stumbled up this page and it has fixed a long standing problem of mine. Cool beans!

Thanks.

6/9/2005 2:09 PM

# re: Intersection of Date Ranges - Hendrik Swanepoel

very cool.

9/8/2005 11:09 PM

# re: Intersection of Date Ranges - Andrew Bennett

Dithermaster's formula is probably clearer when re-stated using DeMorgan's Theorem as:

overlap = (end2 >= start1) && (start2 <= end1);

12/13/2005 9:47 AM

# A formula for how many days overlap - Tom C

overlap = (end1 - start1) - max(end1 - end2,0) - max(start2 - start1,0)

in sql:

DATEDIFF(end1,start1)
- GREATEST(DATEDIFF(end1,end2),0)
- GREATEST(DATEDIFF(start2,start1,0)

12/27/2005 5:08 PM

# re: Intersection of Date Ranges - Dave Koss

Thank You so much. Or as a friend of mine was fond of saying, 'Thanks 'til you're better paid'. Like yourself, I thrashed around the (seemingly simple) problem for a day and went to Google, where your page popped up. I knew as soon as I saw the graphic that I was in the right place. I was looking for a SQL solution and Ryan Jameson's feedback was perfect for the job. Your solution is as elegant as Jacqueline Onassis. Thanks.

4/18/2006 10:11 AM

# re: Intersection of Date Ranges - Abraham

Very, very nice...

5/25/2006 5:12 AM

# re: Intersection of Date Ranges - peter Ms

If requirement change into "cacl duration of an Intersection of Date Ranges". How can do it?

7/26/2006 4:34 AM

# re: Intersection of Date Ranges - Brian

even cleaner...

private bool DatesOverlap( DateTime start1, DateTime end1, DateTime start2, DateTime end2 )
{
return (end1.Ticks >= start2.Ticks) && (end2.Ticks >= start1.Ticks);
}

7/31/2006 4:20 PM

# re: Intersection of Date Ranges - Eric

What about trying to find the start and end datetime of the intersection instead of just determine a boolean if they intersect? Anyone have a solution for that.

Thanks

11/21/2006 11:45 AM

# re: Intersection of Date Ranges - Ryan Farley

Eric,

To get to that, all you'd need to do is get the MAX startdate between rang1 and range2 and the MIN enddate between range1 and range2. That would give you the start and end dates of the intersection.

-Ryan

11/21/2006 11:49 AM

# re: Intersection of Date Ranges - Vince

I like doing it like this to account for all conditions

Dds = data date start
Dde = data date end
Drs = date range start
Dre = date range end

Where
Dds between drs and dre
Or dde between drs and dre
Or dds<drs and dde>dre

This accounts for the four true conditions:
Something starts before the date range and continues into the date range
Something starts in the date range and continues out of the date range
Something starts in date range and ends in date range
Something starts before the date range and ends after the date range

12/21/2006 2:35 PM

# re: Intersection of Date Ranges - MindStorm

Hum... I think its still complicated.

First, you should receive DateTime objects instead of int. But ok.

Then you could do:

private bool intersects(DateTime r1start, DateTime r1end, DateTime r2start, DateTime r2end)
{
return !(r2end <= r1start || r1end <= r2start)
}

If you are skeptical, test it. I've test it with all seven possible cases.

Much better, hein? :)

4/3/2007 3:01 AM

# re: Intersection of Date Ranges - Carlos

I think you've missed one problem, when both DateRange doesn'd intersect at all, it can happens that r1end<r2start because r2 is at the right of r1 and both r2start and r2end are > r1end, and the same from the other side. I think it's neccesary some more conditions:
r2start < r1end && r2start>=r1start|| r2end> r1start && r2end<= r1end.

5/3/2007 2:40 AM

# re: Intersection of Date Ranges - JO

Thanks all

5/29/2007 8:35 AM

# re: Intersection of Date Ranges - Dave Abad

All I can say is a huge thanks to Ryan to putting this in to terms my brain could comprehend. Whoot working code.... moving on.

sql = "SELECT eventid from events WHERE " & _
" (NOT((event_end < '" & request.form("passSDate") & "') OR (event_start >
'" & request.form("passEDate") & "')));"
Set oRS = DBConn.Execute(sql)
if oRS.eof then
sql = "INSERT

Thanks again!

6/6/2007 2:27 PM

# re: Intersection of Date Ranges - Enric

I prefer "Dithermaster method" because I can use it on SQL statement.

But what about the possibility of setting the endDate to NULL. With a date range like that [start, NULL] you indicate that the date range doesn't have end (till infinite). Can you think about a algorithm to check overlappings in that case?

Thanks in advance

7/12/2007 9:55 AM

# re: Intersection of Date Ranges - James T

if one of your ranges doesn't have an end then use something like Isnull(endDate, '2999-01-01') for the end date. In SQL it will use the value given if it's a null. In most programing languages you could use iif(isnull(endDate), '2999-01-01', endDate) to get the same effect.

Technically you just use the maximum date value that the server or language will accept. Although it's probably better to just use a date that's really unlikely to be reached, like 50 or 100 years from now, rather than risking dates that might push the data limits.

8/31/2007 6:35 AM

# re: Intersection of Date Ranges - Will Asrari

Digging this! I implemented range pattern ultimately using DateTime.Hour. Works like a charm!

If I am ever in a position to interview / hire someone I am going to ask the same question your friend asked you and hand the applicant a vis-a-vis and point him / her to the whiteboard.

- Will

10/17/2007 10:06 PM

# Intersection of Date Ranges - Hema

This works great!!!

1/5/2008 4:35 PM

# re: Intersection of Date Ranges - Richard

Thanks to Ryan Jameson! The SQL solution works great.

2/5/2008 8:47 AM

# re: Intersection of Date Ranges - DaveHo

I couldn't for the life of me work this out. Thank you!

2/20/2008 11:30 PM

# re: Intersection of Date Ranges - Daniel B

I have a similar yet different question to solve involving date ranges, and was wondering if someone here had a SQL solution.
Scenario:
"Parent" Table A has StartDate & EndDate
"Child" Table B has Entries with Start & End Dates

I need an efficient query that will return any date ranges in which there are Days in the Table A range that are un-accounted for in Table B.

An example in case what I just typed didn't make sense....
So Transaction A can start on 1/1/08 and end on 1/31/08
And have
Item 1 start on 1/1 and end on 1/15
Item 2 start on 1/20 and end on 1/25
Item 3 start on 1/27 and end on 1/30

And I need to know the dates that are missing (1/16-1/19, 1/26, & 1/31)

Thanks in advance for any help you can offer!

3/5/2008 1:06 PM

# <Keyword> - <Keyword>

When i was at the biginnings of the internet (it was in old 1976 year), we made first sites, they all has design just like that one)).

4/1/2008 1:25 PM

Post Feedback

Title:

Name:

Url:

Comments:

	Enter the word you see:

Remember Me?

Recent Posts

Search

Archives

Archives

Post Categories

Ryan Farley Sites

Feedback

Post Feedback