RSS 2.0 Feed
RSS 2.0


Atom 1.0 Feed
Atom 1.0

  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.




                   



Leave a comment below.

Comments

  1. jaybaz [MS] WebLog 8/19/2004 12:52 PM
    Gravatar
  2. Martin 8/19/2004 1:58 PM
    Gravatar
    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.
  3. Ryan Farley 8/19/2004 2:01 PM
    Gravatar
    Nice Martin. That does add some clarity to the code and makes it easier to read. Thanks.
  4. jaybaz [MS] WebLog 8/19/2004 5:14 PM
    Gravatar
  5. J.M 8/19/2004 3:16 PM
    Gravatar
    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.


  6. Ryan Farley 8/19/2004 3:23 PM
    Gravatar
    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.
  7. Ryan Jameson 8/21/2004 11:13 AM
    Gravatar
    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. Scott 6/9/2005 2:09 PM
    Gravatar
    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.
  9. Hendrik Swanepoel 9/8/2005 11:09 PM
    Gravatar
    very cool.
  10. Andrew Bennett 12/13/2005 9:47 AM
    Gravatar
    Dithermaster's formula is probably clearer when re-stated using DeMorgan's Theorem as:

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

  11. Tom C 12/27/2005 5:08 PM
    Gravatar
    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. Dave Koss 4/18/2006 10:11 AM
    Gravatar
    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.
  13. Abraham 5/25/2006 5:12 AM
    Gravatar
    Very, very nice...
  14. peter Ms 7/26/2006 4:34 AM
    Gravatar
    If requirement change into "cacl duration of an Intersection of Date Ranges". How can do it?
  15. Brian 7/31/2006 4:20 PM
    Gravatar
    even cleaner...

    private bool DatesOverlap( DateTime start1, DateTime end1, DateTime start2, DateTime end2 )
    {
    return (end1.Ticks >= start2.Ticks) && (end2.Ticks >= start1.Ticks);
    }
  16. Eric 11/21/2006 11:45 AM
    Gravatar
    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
  17. Ryan Farley 11/21/2006 11:49 AM
    Gravatar
    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
  18. Vince 12/21/2006 2:35 PM
    Gravatar
    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


  19. MindStorm 4/3/2007 3:01 AM
    Gravatar
    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? :)

  20. Carlos 5/3/2007 2:40 AM
    Gravatar
    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.
  21. JO 5/29/2007 8:35 AM
    Gravatar
    Thanks all
  22. Dave Abad 6/6/2007 2:27 PM
    Gravatar
    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!
  23. Enric 7/12/2007 9:55 AM
    Gravatar
    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
  24. James T 8/31/2007 6:35 AM
    Gravatar
    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.
  25. Will Asrari 10/17/2007 10:06 PM
    Gravatar
    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
  26. Hema 1/5/2008 4:35 PM
    Gravatar
    This works great!!!
  27. Richard 2/5/2008 8:47 AM
    Gravatar
    Thanks to Ryan Jameson! The SQL solution works great.
  28. DaveHo 2/20/2008 11:30 PM
    Gravatar
    I couldn't for the life of me work this out. Thank you!
  29. Daniel B 3/5/2008 1:06 PM
    Gravatar
    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!
  30. KP 8/11/2008 3:42 AM
    Gravatar
    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

  31. Techno_Dex 8/29/2008 12:44 PM
    Gravatar
    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)
  32. ASP Net 2.0 Migration 9/4/2008 12:14 AM
    Gravatar
    Thanks for the great post...
  33. newbiej 9/25/2008 6:51 AM
    Gravatar
    how to translate the code into vb.net?
  34. Kseniya 1/17/2009 3:50 PM
    Gravatar
    Thanks for the great post.
    Really, all ingenious is simple.
  35. justin 7/6/2009 11:25 AM
    Gravatar
    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?
  36. justin 7/6/2009 11:25 AM
    Gravatar
    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?
  37. AlienationZombie 7/14/2009 12:39 AM
    Gravatar
    My 10cents worth:

    (NOT (ENDDATE1 < STARTDATE2) AND
    ((ENDDATE1 >= STARTDATE2) AND (ENDDATE1 <= ENDDATE2)) OR
    ((STARTDATE1 >= STARTDATE2) AND (STARTDATE1 <= ENDDATE2)) OR
    ((STARTDATE1 <= STARTDATE2) AND (ENDDATE1 >= ENDDATE2)))
  38. zeuben 7/21/2009 6:17 PM
    Gravatar
    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') ) )
  39. Richard Quadling 9/18/2009 1:49 AM
    Gravatar
    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.

  40. Richard Quadling 9/18/2009 2:24 AM
    Gravatar
    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
  41. Ahmed Metwally 10/20/2009 6:53 AM
    Gravatar
    I done it by just this


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

  42. David 11/15/2009 4:27 PM
    Gravatar
    Thanks, that is nice.

  43. Şahap Aşçı 12/1/2009 7:16 AM
    Gravatar
    for c#;

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

    ----------------------
    for SQL;
    SELECT
    .... FROM ...
    WHERE
    ....
    AND NOT (End1 < Start2 OR Start1 > End2)
  44. Phil Deibel 4/21/2010 10:55 AM
    Gravatar
    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)
  45. sameer 6/9/2010 1:16 AM
    Gravatar


    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 ?
  46. Robert Lerner 6/29/2010 10:20 AM
    Gravatar
    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.
  47. L0is 7/12/2010 1:08 PM
    Gravatar
    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?
  48. 123 8/3/2010 2:16 AM
    Gravatar
    Hi!
  49. 3/17/2012 8:40 PM
    Gravatar
    Intersection of Date Ranges | All Fixes
  50. 8/12/2012 11:38 AM
    Gravatar
    Sangem Chaitanya Blog &amp;raquo; Intersection of Date Ranges
  51. 12/9/2014 6:39 AM
    Gravatar
    VB.NET Array Intersection | Yuhas Answers
Comments have been closed on this topic.



 

News


Also see my CRM Developer blog

Connect:              


Sponsor

Sections