Algorithm to detect overlapping periods

Question

I ve to detect if two time periods are overlapping  Every period has a start date and an end date  I need to detect if my first time period  A  is overlapping with another one B C    In my case  if the start of B is equal to the end of A  they are not overlapping the inverse too   I found the following cases     So actually I m doing this like this   tStartA  lt  tStartB  amp  amp  tStartB  lt  tEndA   For case 1 OR tStartA  lt  tEndB  amp  amp  tEndB  lt   tEndA   For case 2 OR tStartB  lt  tStartA   amp  amp  tEndB  gt  tEndA   For case 3    The case 4 is taken in the account either in case 1 or in case 2   It works  but it seems not very efficient   So  first is there an existing class in c  that can modelize this a time period   something like a timespan  but with a fixed start date   Secondly  Is there already a c  code like in the DateTime class  which can handle this   Third  if no  what would be your approach to make this comparison the most fast

User · Answer

You can create a reusable Range pattern class :

public class Range<T> where T : IComparable
{
    readonly T min;
    readonly T max;

    public Range(T min, T max)
    {
        this.min = min;
        this.max = max;
    }

    public bool IsOverlapped(Range<T> other)
    {
        return Min.CompareTo(other.Max) < 0 && other.Min.CompareTo(Max) < 0;
    }

    public T Min { get { return min; } }
    public T Max { get { return max; } }
}

You can add all methods you need to merge ranges, get intersections and so on...

User · Answer

This code checks if two intervals overlap  --------- ---  --- ---                  gt  FALSE xxxxxxxxxxxxxxxxxxxxxxxxx ------- ---  --- ---                  gt  FALSE xxxxxxxxxxxxxxxxxxxxxxxxx ------ ---  --- ---                  gt  TRUE xxxxxxxxxxxxxxxxxxxxxxxxx --- ---  --- --                   gt  TRUE xxxxxxxxxxxxxxxxxxxxxxxxx ---- ---  --- -----                gt  TRUE xxxxxxxxxxxxxxxxxxxxxxxxx --- ---  ---- -                   gt  TRUE xxxxxxxxxxxxxxxxxxxxxxxxx --- ---  ---- --                  gt  TRUE xxxxxxxxxxxxxxxxxxxxxxxxx --- ---  --- ---                  gt  TRUE xxxxxxxxxxxxxxxxxxxxxxxxx --- ---  ---- ---                 gt  TRUE xxxxxxxxxxxxxxxxxxxxxxxxx --- ---  ------- ---              gt  FALSE xxxxxxxxxxxxxxxxxxxxxxxxx --- ---  -------- ---             gt  FALSE  Algorithm  x1  lt  y2 and x2  gt  y1  example 12 00 - 12 30 is not overlapping with 12 30 13 00

User · Answer

--logic FOR OVERLAPPING DATES DECLARE  StartDate datetime  --Reference start date DECLARE  EndDate datetime    --Reference end date DECLARE  NewStartDate datetime --New Start date DECLARE  NewEndDate datetime   --New End Date  Select   Case      when  StartDate is null          then  NewStartDate     when   StartDate lt  NewStartDate and   EndDate  lt   NewStartDate          then  NewStartDate     when   StartDate lt  NewStartDate and   EndDate  gt   NewEndDate          then  NewStartDate     when   StartDate lt  NewStartDate and   EndDate  gt   NewStartDate          then  NewStartDate       when   StartDate gt  NewStartDate and   NewEndDate  lt   StartDate          then  NewStartDate     else  StartDate end  as StartDate      Case      when  EndDate is null            then  NewEndDate     when   EndDate gt  NewEndDate and  Startdate  lt   NewEndDate          then  NewEndDate     when   EndDate gt  NewEndDate and  Startdate  gt   NewEndDate          then  NewEndDate     when   EndDate lt  NewEndDate and  NewStartDate  gt   EndDate          then  NewEndDate     else  EndDate end  as EndDate   Distrubution logic

User · Answer

I don t believe that the framework itself has this class  Maybe a third-party library     But why not create a Period value-object class to handle this complexity  That way you can ensure other constraints  like validating start vs end datetimes  Something like   using System  using System Collections Generic  using System Linq  using System Text   namespace Whatever Domain Timing       public class Period           public DateTime StartDateTime  get  private set           public DateTime EndDateTime  get  private set            public Period DateTime StartDateTime  DateTime EndDateTime                if  StartDateTime  gt  EndDateTime                  throw new InvalidPeriodException  End DateTime Must Be Greater Than Start DateTime                 this StartDateTime   StartDateTime              this EndDateTime   EndDateTime                      public bool Overlaps Period anotherPeriod               return  this StartDateTime  lt  anotherPeriod EndDateTime  amp  amp  anotherPeriod StartDateTime  lt  this EndDateTime                     public TimeSpan GetDuration                return EndDateTime - StartDateTime                        public class InvalidPeriodException   Exception           public InvalidPeriodException string Message    base Message                    That way you will be able to individually compare each period

User · Answer

Simple check to see if two time periods overlap   bool overlap   a start  lt  b end  amp  amp  b start  lt  a end    or in your code   bool overlap   tStartA  lt  tEndB  amp  amp  tStartB  lt  tEndA     Use  lt   instead of  lt  if you change your mind about wanting to say that two periods that just touch each other overlap

User · Answer

I m building a booking system and found this page  I m interested in range intersection only  so I built this structure  it is enough to play with DateTime ranges   You can check Intersection and check if a specific date is in range  and get the intersection type and the most important  you can get intersected Range   public struct DateTimeRange         region Construction     public DateTimeRange DateTime start  DateTime end            if  start gt end                throw new Exception  Invalid range edges                        Start   start           End   end             endregion       region Properties     private DateTime  Start       public DateTime Start           get   return  Start            private set    Start   value              private DateTime  End       public DateTime End           get   return  End            private set    End   value               endregion       region Operators     public static bool operator    DateTimeRange range1  DateTimeRange range2            return range1 Equals range2              public static bool operator    DateTimeRange range1  DateTimeRange range2            return   range1    range2             public override bool Equals object obj            if  obj is DateTimeRange                var range1   this              var range2    DateTimeRange obj              return range1 Start    range2 Start  amp  amp  range1 End    range2 End                    return base Equals obj             public override int GetHashCode             return base GetHashCode               endregion       region Querying     public bool Intersects DateTimeRange range            var type   GetIntersectionType range           return type    IntersectionType None            public bool IsInRange DateTime date            return  date  gt   this Start   amp  amp   date  lt   this End             public IntersectionType GetIntersectionType DateTimeRange range            if  this    range                return IntersectionType RangesEqauled                    else if  IsInRange range Start   amp  amp  IsInRange range End                 return IntersectionType ContainedInRange                    else if  IsInRange range Start                 return IntersectionType StartsInRange                    else if  IsInRange range End                 return IntersectionType EndsInRange                    else if  range IsInRange this Start   amp  amp  range IsInRange this End                 return IntersectionType ContainsRange                    return IntersectionType None            public DateTimeRange GetIntersection DateTimeRange range            var type   this GetIntersectionType range           if  type    IntersectionType RangesEqauled    type  IntersectionType ContainedInRange                return range                    else if  type    IntersectionType StartsInRange                return new DateTimeRange range Start  this End                     else if  type    IntersectionType EndsInRange                return new DateTimeRange this Start  range End                     else if  type    IntersectionType ContainsRange                return this                    else               return default DateTimeRange                        endregion       public override string ToString             return Start ToString       -     End ToString            public enum IntersectionType            lt summary gt          No Intersection          lt  summary gt      None   -1           lt summary gt          Given range ends inside the range          lt  summary gt      EndsInRange           lt summary gt          Given range starts inside the range          lt  summary gt      StartsInRange           lt summary gt          Both ranges are equaled          lt  summary gt      RangesEqauled           lt summary gt          Given range contained in the range          lt  summary gt      ContainedInRange           lt summary gt          Given range contains the range          lt  summary gt      ContainsRange

User · Answer

Check this simple method  It is recommended to put This method in your dateUtility  public static bool isOverlapDates DateTime dtStartA  DateTime dtEndA  DateTime dtStartB  DateTime dtEndB                        return dtStartA  lt  dtEndB  amp  amp  dtStartB  lt  dtEndA

User · Answer

public class ConcreteClassModel   BaseModel       rest of class  public bool InersectsWith ConcreteClassModel crm                return   this StartDateDT  gt  crm EndDateDT    this EndDateDT  lt  crm StartDateDT             TestClass  public class ConcreteClassTest        TestMethod      public void TestConcreteClass IntersectsWith                 var sutPeriod   new ConcreteClassModel     StartDateDT   new DateTime 2016  02  01   EndDateDT   new DateTime 2016  02  29              var periodBeforeSutPeriod   new ConcreteClassModel     StartDateDT   new DateTime 2016  01  01   EndDateDT   new DateTime 2016  01  31             var periodWithEndInsideSutPeriod   new ConcreteClassModel     StartDateDT   new DateTime 2016  01  10   EndDateDT   new DateTime 2016  02  10             var periodSameAsSutPeriod   new ConcreteClassModel     StartDateDT   new DateTime 2016  02  01   EndDateDT   new DateTime 2016  02  29              var periodWithEndDaySameAsStartDaySutPeriod   new ConcreteClassModel     StartDateDT   new DateTime 2016  01  01   EndDateDT   new DateTime 2016  02  01             var periodWithStartDaySameAsEndDaySutPeriod   new ConcreteClassModel     StartDateDT   new DateTime 2016  02  29   EndDateDT   new DateTime 2016  03  31             var periodEnclosingSutPeriod   new ConcreteClassModel     StartDateDT   new DateTime 2016  01  01   EndDateDT   new DateTime 2016  03  31              var periodWithinSutPeriod   new ConcreteClassModel     StartDateDT   new DateTime 2016  02  010   EndDateDT   new DateTime 2016  02  20             var periodWithStartInsideSutPeriod   new ConcreteClassModel     StartDateDT   new DateTime 2016  02  10   EndDateDT   new DateTime 2016  03  10             var periodAfterSutPeriod   new ConcreteClassModel     StartDateDT   new DateTime 2016  03  01   EndDateDT   new DateTime 2016  03  31              Assert IsFalse sutPeriod InersectsWith periodBeforeSutPeriod    sutPeriod InersectsWith periodBeforeSutPeriod  should be false            Assert IsTrue sutPeriod InersectsWith periodWithEndInsideSutPeriod    sutPeriod InersectsWith periodEndInsideSutPeriod should be true            Assert IsTrue sutPeriod InersectsWith periodSameAsSutPeriod    sutPeriod InersectsWith periodSameAsSutPeriod  should be true             Assert IsTrue sutPeriod InersectsWith periodWithEndDaySameAsStartDaySutPeriod    sutPeriod InersectsWith periodWithEndDaySameAsStartDaySutPeriod  should be true            Assert IsTrue sutPeriod InersectsWith periodWithStartDaySameAsEndDaySutPeriod    sutPeriod InersectsWith periodWithStartDaySameAsEndDaySutPeriod  should be true            Assert IsTrue sutPeriod InersectsWith periodEnclosingSutPeriod    sutPeriod InersectsWith periodEnclosingSutPeriod  should be true             Assert IsTrue sutPeriod InersectsWith periodWithinSutPeriod    sutPeriod InersectsWith periodWithinSutPeriod  should be true            Assert IsTrue sutPeriod InersectsWith periodWithStartInsideSutPeriod    sutPeriod InersectsWith periodStartInsideSutPeriod  should be true            Assert IsFalse sutPeriod InersectsWith periodAfterSutPeriod    sutPeriod InersectsWith periodAfterSutPeriod  should be false              Thanks for the above answers which help me code the above for an MVC project   Note StartDateDT and EndDateDT are dateTime types

User · Answer

Try this   This method will determine if  two  date spans are overlapping  regardless of the ordering of the method s input arguments   This can also be used with more than two date spans  by individually checking each date span combination  ex  with 3 date spans  run span1 against span2  span2 against span3  and span1 against span3    public static class HelperFunctions       public static bool AreSpansOverlapping Tuple lt DateTime DateTime gt  span1  Tuple lt DateTime DateTime gt  span2  bool includeEndPoints                if  span1    null    span2    null                        return false                    else if   new DateTime     span1 Item1  span1 Item2  span2 Item1  span2 Item2    Any v   gt  v    DateTime MinValue                         return false                    else                       if  span1 Item1  gt  span1 Item2                                span1   new Tuple lt DateTime  DateTime gt  span1 Item2  span1 Item1                             if  span2 Item1  gt  span2 Item2                                span2   new Tuple lt DateTime  DateTime gt  span2 Item2  span2 Item1                              if  includeEndPoints                                return                                          span1 Item1  lt   span2 Item1  amp  amp  span1 Item2  gt   span2 Item1                           span1 Item1  lt   span2 Item2  amp  amp  span1 Item2  gt   span2 Item2                                              span2 Item1  lt   span1 Item1  amp  amp  span2 Item2  gt   span1 Item1                           span2 Item1  lt   span1 Item2  amp  amp  span2 Item2  gt   span1 Item2                                                else                               return                                          span1 Item1  lt  span2 Item1  amp  amp  span1 Item2  gt  span2 Item1                           span1 Item1  lt  span2 Item2  amp  amp  span1 Item2  gt  span2 Item2                                              span2 Item1  lt  span1 Item1  amp  amp  span2 Item2  gt  span1 Item1                           span2 Item1  lt  span1 Item2  amp  amp  span2 Item2  gt  span1 Item2                                             span1 Item1    span2 Item1  amp  amp  span1 Item2    span2 Item2                                                       Test   static void Main string   args          Random r   new Random         DateTime d1      DateTime d2      DateTime d3      DateTime d4       for  int i   0  i  lt  100  i                  d1   new DateTime 2012 1  r Next 1 31            d2   new DateTime 2012 1  r Next 1 31            d3   new DateTime 2012 1  r Next 1 31            d4   new DateTime 2012 1  r Next 1 31             Console WriteLine  span1       d1 ToShortDateString       to     d2 ToShortDateString             Console WriteLine  span2       d3 ToShortDateString       to     d4 ToShortDateString             Console Write   t            Console WriteLine HelperFunctions AreSpansOverlapping              new Tuple lt DateTime  DateTime gt  d1  d2               new Tuple lt DateTime  DateTime gt  d3  d4               true      or use False  to ignore span s endpoints               ToString             Console WriteLine               Console WriteLine  COMPLETE        System Console ReadKey

User · Answer

There is a wonderful library with good reviews on CodeProject  http   www codeproject com Articles 168662 Time-Period-Library-for-NET  That library does a lot of work concerning overlap  intersecting them  etc  It s too big to copy paste all of it  but I ll see which specific parts which can be useful to you

User · Answer

This is my solution  public static bool OverlappingPeriods DateTime aStart  DateTime aEnd                                        DateTime bStart  DateTime bEnd        if  aStart  gt  aEnd          throw new ArgumentException  quot A start can not be after its end  quot         if bStart  gt  bEnd          throw new ArgumentException  quot B start can not be after its end  quot         return    aEnd  lt  bStart  amp  amp  aStart  lt  bStart                      bEnd  lt  aStart  amp  amp  bStart  lt  aStart       I unit tested it with 100  coverage

User · Answer

How about a custom interval-tree structure  You ll have to tweak it a little bit to define what it means for two intervals to  overlap  in your domain   This question might help you find an off-the-shelf interval-tree implementation in C

[c#] Algorithm to detect overlapping periods

Examples related to c#

Examples related to .net

Examples related to algorithm

Examples related to datetime

Examples related to time