Thursday 6 December 2012

Find Overlapping Date Ranges



I recently had to implement a "DateRange" validator to check for any overlaps in the date ranges.

Here is my approach to it :

I started with a custom DateRange class.
 
public class DateRange
{
    public int SortOrder { get; set; }
    public DateTime Start { get; set; }
    public DateTime End { get; set; }

    public DateRange() {}

    public DateRange(DateTime sTime, DateTime eTime)
    {
        Start = sTime;
        End = eTime;
    }
} 

Then I call the "HasOverlap" method on my validator to check for overlaps.
 
/*
* LOGIC:
* 
* 1. Take a List of date ranges. Example:
            [Tuple A]         --------         [Sort Order 1]
            [Tuple B]--------                  [Sort Order 2]
            [Tuple C]     --------             [Sort Order 3]
            [Tuple D]     --------             [Sort Order 4]
            [Tuple E]             --------     [Sort Order 5]
            [Tuple F]     ----------           [Sort Order 6]
         
* 2. Now sort the range by start + End Dates. This results in:
            [Tuple B]--------                  [Sort Order 1]
            [Tuple C]     --------             [Sort Order 2]
            [Tuple D]     --------             [Sort Order 3]
            [Tuple F]     ----------           [Sort Order 4]
            [Tuple A]         --------         [Sort Order 5]
            [Tuple E]             --------     [Sort Order 6]    
         
* 3. The Logic is that there will be an overlap IF EVEN ONE of 
*    the 2 base conditions are met:
*      (a) After sorting the list, a given tuple (TUPLE X) 
*          will be deemed overlapping 
*              if the END-DATE of (TUPLE X) is GREATER THAN the START-DATE 
*              of ANY tuple WHERE the sort order is GREATER THAN that of (TUPLE X)
*          
*      --- OR ---
*      
*      (b) After sorting the list, a given tuple (TUPLE X) 
*          will be deemed overlapping 
*              if the START-DATE and END-DATE of (TUPLE X) MATCHES 
*              the START-DATE and END-DATE of ANY tuple 
*              WHERE the sort order is GREATER THAN that of (TUPLE X)
*/
private bool HasOverlap(IList<DateRange> ranges)
{
    // 1. Sort Dates based on Start & End Dates
    var sortedRange = ranges
                        .OrderBy(p => p.Start)
                        .ThenBy(p => p.End)
                        .ToList();

    var sortCounter = 0;
    sortedRange.ForEach(e =>
    {
        e.SortOrder = sortCounter;
        sortCounter++;
    });


    // 2. Check if the end dates are > any start dates except the same one 
    return sortedRange
        .Any(tuple => (from innerLoop in sortedRange
                        where (
                                tuple.End > innerLoop.Start &&
                                innerLoop.SortOrder > tuple.SortOrder
                                ) ||
                                (
                                tuple.End == innerLoop.End &&
                                tuple.Start == innerLoop.Start &&
                                innerLoop.SortOrder > tuple.SortOrder
                                )
                        select innerLoop).Any());
}

Additionally I also pass my DateRanges through a sanity check to ensure that the start < end dates.


No comments:

Post a Comment