Intersection of Date Ranges

Thursday, August 19, 2004 8:51 AM Filed under:

General

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.

Comments

jaybaz [MS] WebLog 8/19/2004 12:52 PM
Martin 8/19/2004 1:58 PM

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.
Ryan Farley 8/19/2004 2:01 PM

Nice Martin. That does add some clarity to the code and makes it easier to read. Thanks.
jaybaz [MS] WebLog 8/19/2004 5:14 PM
J.M 8/19/2004 3:16 PM

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.
Ryan Farley 8/19/2004 3:23 PM

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.
Ryan Jameson 8/21/2004 11:13 AM

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)))
---------------------------------------------------------------------------------------
Scott 6/9/2005 2:09 PM

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.
Hendrik Swanepoel 9/8/2005 11:09 PM

very cool.
Andrew Bennett 12/13/2005 9:47 AM

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

overlap = (end2 >= start1) && (start2 <= end1);
Tom C 12/27/2005 5:08 PM

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)
Dave Koss 4/18/2006 10:11 AM

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.
Abraham 5/25/2006 5:12 AM

Very, very nice...
peter Ms 7/26/2006 4:34 AM

If requirement change into "cacl duration of an Intersection of Date Ranges". How can do it?
Brian 7/31/2006 4:20 PM

even cleaner...

private bool DatesOverlap( DateTime start1, DateTime end1, DateTime start2, DateTime end2 )
{
return (end1.Ticks >= start2.Ticks) && (end2.Ticks >= start1.Ticks);
}
Eric 11/21/2006 11:45 AM

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
Ryan Farley 11/21/2006 11:49 AM

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
Vince 12/21/2006 2:35 PM

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
MindStorm 4/3/2007 3:01 AM

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? :)
Carlos 5/3/2007 2:40 AM

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.
JO 5/29/2007 8:35 AM

Thanks all
Dave Abad 6/6/2007 2:27 PM

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!
Enric 7/12/2007 9:55 AM

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
James T 8/31/2007 6:35 AM

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.
Will Asrari 10/17/2007 10:06 PM

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
Hema 1/5/2008 4:35 PM

This works great!!!
Richard 2/5/2008 8:47 AM

Thanks to Ryan Jameson! The SQL solution works great.
DaveHo 2/20/2008 11:30 PM

I couldn't for the life of me work this out. Thank you!
Daniel B 3/5/2008 1:06 PM

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!
KP 8/11/2008 3:42 AM

No Carlos, it's NOT necessary to put in extra checks. The non-overlapping scenario's ARE included in the short formula

(end2 >= start1) && (start2 <= end1).

Depending on what data may occur or may be valid in your application, or the datatype or programming language you're using, you might add additional checks for NULL's however. E.g. your application might support open ranges, e.g. implemented as the start/endpoint being null.
(it's just OR-ing some additional end2 == null and similar other checks in the above formula). If open ranges don't occur, or they're not implemented as null, but as a very small and/or very large value, it may just work already
Techno_Dex 8/29/2008 12:44 PM

Before point to another site (i.e. Jay Bazuzi's solution) it's good idea to make sure it actually works. The following statement makes no sense and will always return the same result.

if (left.Start.CompareTo(left.Start) == 0)
ASP Net 2.0 Migration 9/4/2008 12:14 AM

Thanks for the great post...
newbiej 9/25/2008 6:51 AM

how to translate the code into vb.net?
Kseniya 1/17/2009 3:50 PM

Thanks for the great post.
Really, all ingenious is simple.
justin 7/6/2009 11:25 AM

not to bring up an old topic, but I'm doing something similar today and found your algorithm. I don't think it works in the following two cases:

range 1: 5am-7am
range 2: 7am - 11am

range 1: 11am - 4pm
range 2: 7am - 11am

your algorithm returns true, and perhaps this is by design? I guess the question is do you consider it an intersection if that is absolute no overlap?
justin 7/6/2009 11:25 AM

not to bring up an old topic, but I'm doing something similar today and found your algorithm. I don't think it works in the following two cases:

range 1: 5am-7am
range 2: 7am - 11am

range 1: 11am - 4pm
range 2: 7am - 11am

your algorithm returns true, and perhaps this is by design? I guess the question is do you consider it an intersection if that is absolute no overlap?
AlienationZombie 7/14/2009 12:39 AM

My 10cents worth:

(NOT (ENDDATE1 < STARTDATE2) AND
((ENDDATE1 >= STARTDATE2) AND (ENDDATE1 <= ENDDATE2)) OR
((STARTDATE1 >= STARTDATE2) AND (STARTDATE1 <= ENDDATE2)) OR
((STARTDATE1 <= STARTDATE2) AND (ENDDATE1 >= ENDDATE2)))
zeuben 7/21/2009 6:17 PM

in MySQL:

SELECT DISTINCT s.* from schedule AS s

WHERE (
('2009-07-22 12:00:00' = s.schedule_start)
OR ( ('2009-07-22 12:00:00' > s.schedule_start ) AND ('2009-07-22 12:00:00' <= s.schedule_end) )
OR ( ('2009-07-22 12:00:00' < s.schedule_start ) AND (s.schedule_start <= '2009-07-23 02:00:00') ) )
Richard Quadling 9/18/2009 1:49 AM

Great article. It seems that the test can be reduced.

Here is a PHP script with all the test cases I could think of ...

<?php
function intersect($start1, $end1, $start2, $end2) {
// Original test.
// return ($start1 == $start2) || ($start1 > $start2 ? $start1 <= $end2 : $start2 <= $end1);

// Reduced test.
return ($start1 >= $start2) ? ($start1 <= $end2) : ($start2 <= $end1);
}

$tests = array (
'First is on the far left ' => array(1, 2, 8, 9, False),
'First is on the far right' => array(8, 9, 1, 2, False),
'Identical ' => array(1, 9, 1, 9, True),
'Same start ' => array(1, 5, 1, 9, True),
'Same end ' => array(1, 9, 5, 9, True),
'First contains second ' => array(1, 9, 3, 7, True),
'Second contains first ' => array(3, 7, 1, 9, True),
'First end within second ' => array(1, 7, 3, 9, True),
'First start within second' => array(3, 9, 1, 7, True),
'First continues to second' => array(1, 5, 5, 9, True),
'Second continues to first' => array(5, 9, 1, 5, True),
);

foreach($tests as $test => $testData) {
list($start1, $end1, $start2, $end2, $expected) = $testData;
$intersects = intersect($start1, $end1, $start2, $end2);
echo
$test,
' Expected ', ($expected ? 'True ' : 'False'),
' Result ', ($intersects ? 'True ' : 'False'),
($expected === $intersects ? ' Passed' : ' Failed'),
PHP_EOL;
}

And the results ...

First is on the far left Expected False Result False Passed
First is on the far right Expected False Result False Passed
Identical Expected True Result True Passed
Same start Expected True Result True Passed
Same end Expected True Result True Passed
First contains second Expected True Result True Passed
Second contains first Expected True Result True Passed
First end within second Expected True Result True Passed
First start within second Expected True Result True Passed
First continues to second Expected True Result True Passed
Second continues to first Expected True Result True Passed

My only issue with this code is the ability to describe ranges that continue from each other.

The last 2 tests I would like to be able to return false on.

Range 1 is from 1 to 2
Range 2 is from 2 to 3

These could be considered as NON overlapping.

Currently both tests give the same result.

A word of warning, the ranges are inclusive. A range like 5,1 would mess things up a lot.
Richard Quadling 9/18/2009 2:24 AM

Being anal about testing, I've put all the tests above into PHP.

Interesting results.

TomC's tests isn't a true/false return, so essentially "fail", but it is for a different purpose I think.

Carlos's test fails when the second range contains the first range.

Strangely enough Carlos and Mindstorm's test both fail when the ranges are continous - which is actually what I'd want in a part of my code.

The code below is for PHP5.3.0 (uses closures which is 5.3.0+ only).

Only failures are reported.

So, for me, Mindstorm's test is the one I'd use for checking ranges.

[EDITED] I think my post is too big with the code.

If you want the code, email me at RQuadling at that nice google mail dot com place.

Results:

First is on the far left Expected FalseTom C:-6
First is on the far right Expected FalseTom C:-6
Identical Expected True Tom C:8
Same start Expected True Tom C:4
Same end Expected True Tom C:4
First contains second Expected True Tom C:4
Second contains first Expected True Tom C:4 Carlos:False
First end within second Expected True Tom C:4
First start within second Expected True Tom C:4
First continues to second Expected True Tom C:0 Mindstorm:False Carlos:False
Second continues to first Expected True Tom C:0 Mindstorm:False Carlos:False
Ahmed Metwally 10/20/2009 6:53 AM

I done it by just this

if(End1 <= Start2 || Start1 >= End2)
{
string result = "Not Intersected.";
}
David 11/15/2009 4:27 PM

Thanks, that is nice.
Şahap Aşçı 12/1/2009 7:16 AM

for c#;

if(!(End1 < Start2 || Start1 > End2))
{
string result = "Intersected.";
}

----------------------
for SQL;
SELECT
.... FROM ...
WHERE
....
AND NOT (End1 < Start2 OR Start1 > End2)
Phil Deibel 4/21/2010 10:55 AM

All these comments work for comparing just 2 dates, but I am working with a list of ranges that have to be compared to each other throughout and provide a false if any two ranges in the list overlap. I was trying to use a lambda expression but that fails when it checks against itself.
Sounds simple, but really giving me a pain.

All that I have available coming in is the list of ranges. (could contain one range or many)

Any ideas? (C# code preferred)
sameer 6/9/2010 1:16 AM

I have a string (R(46 - 9900)) AND ( NOT (R(48 - 9900))) where R denotes Range . If you evaluate the expression it results in R(46-47) , considering the logical operators (AND,NOT).

I have a requirement where I need to parse such a string and evaluate it to a correct result . I have to use C++ as a programming tool to achieve this result .

Can you suggest a few guide lines as to how do I proceed on this ?
Robert Lerner 6/29/2010 10:20 AM

I could seriously kiss you right now. You have no idea all the ways I attempted doing this. Putting seconds into an array, doing an array flip, searching for key with isset -- basic math, etc.

Nice job.
L0is 7/12/2010 1:08 PM

Thanks sooooooo much! I'm trying to apply this to Sharepoint where I have a start date and an end date and I'd like to see if any of those dates fall into this week.

Basically I have a simple attendance list and want to see who is out this week. I have a Start Week Filter field and End Week Filter field which calculates the start and end of the work week based on the start date and end dates.

Can this be done using how I have my list set up?
123 8/3/2010 2:16 AM

Hi!
3/17/2012 8:40 PM

Intersection of Date Ranges | All Fixes
8/12/2012 11:38 AM

Sangem Chaitanya Blog &raquo; Intersection of Date Ranges
12/9/2014 6:39 AM

VB.NET Array Intersection | Yuhas Answers