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 < tStartB && tStartB < tEndA //For case 1
OR
tStartA < tEndB && tEndB <= tEndA //For case 2
OR
tStartB < tStartA  && tEndB > 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?

Answer 1

Simple check to see if two time periods overlap:

bool overlap = a.start < b.end && b.start < a.end;

or in your code:

bool overlap = tStartA < tEndB && tStartB < tEndA;

(Use <= instead of < if you change your mind about wanting to say that two periods that just touch each other overlap.)

Answer 2

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.

Answer 3

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

Answer 4

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>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 && 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 >= this.Start) && (date <= this.End);
    }
    public IntersectionType GetIntersectionType(DateTimeRange range) {
        if (this == range) {
            return IntersectionType.RangesEqauled;
        }
        else if (IsInRange(range.Start) && 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) && 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
{
    /// <summary>
    /// No Intersection
    /// </summary>
    None = -1,
    /// <summary>
    /// Given range ends inside the range
    /// </summary>
    EndsInRange,
    /// <summary>
    /// Given range starts inside the range
    /// </summary>
    StartsInRange,
    /// <summary>
    /// Both ranges are equaled
    /// </summary>
    RangesEqauled,
    /// <summary>
    /// Given range contained in the range
    /// </summary>
    ContainedInRange,
    /// <summary>
    /// Given range contains the range
    /// </summary>
    ContainsRange,
}

Answer 5

This code checks if two intervals overlap.

---------|---|
---|---|                > FALSE
xxxxxxxxxxxxxxxxxxxxxxxxx
-------|---|
---|---|                > FALSE
xxxxxxxxxxxxxxxxxxxxxxxxx
------|---|
---|---|                > TRUE
xxxxxxxxxxxxxxxxxxxxxxxxx
---|---|
---|--|                 > TRUE
xxxxxxxxxxxxxxxxxxxxxxxxx
----|---|
---|-----|              > TRUE
xxxxxxxxxxxxxxxxxxxxxxxxx
---|---|
----|-|                 > TRUE
xxxxxxxxxxxxxxxxxxxxxxxxx
---|---|
----|--|                > TRUE
xxxxxxxxxxxxxxxxxxxxxxxxx
---|---|
---|---|                > TRUE
xxxxxxxxxxxxxxxxxxxxxxxxx
---|---|
----|---|               > TRUE
xxxxxxxxxxxxxxxxxxxxxxxxx
---|---|
-------|---|            > FALSE
xxxxxxxxxxxxxxxxxxxxxxxxx
---|---|
--------|---|           > FALSE

Algorithm:

x1 < y2
and
x2 > y1

example 12:00 - 12:30 is not overlapping with 12:30 13:00

Answer 6

This is my solution:

public static bool OverlappingPeriods(DateTime aStart, DateTime aEnd,
                                      DateTime bStart, DateTime bEnd)
{
    if (aStart > aEnd)
        throw new ArgumentException("A start can not be after its end.");

    if(bStart > bEnd)
        throw new ArgumentException("B start can not be after its end.");

    return !((aEnd < bStart && aStart < bStart) ||
                (bEnd < aStart && bStart < aStart));
}

I unit tested it with 100% coverage.

Answer 7

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#.

Answer 8

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 > 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 < anotherPeriod.EndDateTime && anotherPeriod.StartDateTime < 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...

Answer 9

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<DateTime,DateTime> span1, Tuple<DateTime,DateTime> span2, bool includeEndPoints)
    {
        if (span1 == null || span2 == null)
        {
            return false;
        }
        else if ((new DateTime[] { span1.Item1, span1.Item2, span2.Item1, span2.Item2 }).Any(v => v == DateTime.MinValue))
        {
            return false;
        }
        else
        {
            if (span1.Item1 > span1.Item2)
            {
                span1 = new Tuple<DateTime, DateTime>(span1.Item2, span1.Item1);
            }
            if (span2.Item1 > span2.Item2)
            {
                span2 = new Tuple<DateTime, DateTime>(span2.Item2, span2.Item1);
            }

            if (includeEndPoints)
            {
                return 
                ((
                    (span1.Item1 <= span2.Item1 && span1.Item2 >= span2.Item1) 
                    || (span1.Item1 <= span2.Item2 && span1.Item2 >= span2.Item2)
                ) || (
                    (span2.Item1 <= span1.Item1 && span2.Item2 >= span1.Item1) 
                    || (span2.Item1 <= span1.Item2 && span2.Item2 >= span1.Item2)
                ));
            }
            else
            {
                return 
                ((
                    (span1.Item1 < span2.Item1 && span1.Item2 > span2.Item1) 
                    || (span1.Item1 < span2.Item2 && span1.Item2 > span2.Item2)
                ) || (
                    (span2.Item1 < span1.Item1 && span2.Item2 > span1.Item1) 
                    || (span2.Item1 < span1.Item2 && span2.Item2 > span1.Item2)
                ) || (
                    span1.Item1 == span2.Item1 && 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 < 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<DateTime, DateTime>(d1, d2),
            new Tuple<DateTime, DateTime>(d3, d4),
            true    //or use False, to ignore span's endpoints
            ).ToString());
        Console.WriteLine();
    }

    Console.WriteLine("COMPLETE");
    System.Console.ReadKey();
}

Answer 10

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 < dtEndB && dtStartB < dtEndA;
        }

Answer 11

public class ConcreteClassModel : BaseModel
{
... rest of class

public bool InersectsWith(ConcreteClassModel crm)
    {
        return !(this.StartDateDT > crm.EndDateDT || this.EndDateDT < 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

Answer 12

--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<@NewStartDate and  @EndDate < @NewStartDate)
        then @NewStartDate
    when (@StartDate<@NewStartDate and  @EndDate > @NewEndDate)
        then @NewStartDate
    when (@StartDate<@NewStartDate and  @EndDate > @NewStartDate)
        then @NewStartDate  
    when (@StartDate>@NewStartDate and  @NewEndDate < @StartDate)
        then @NewStartDate
    else @StartDate end) as StartDate,  

(Case 
    when @EndDate is null   
        then @NewEndDate
    when (@EndDate>@NewEndDate and @Startdate < @NewEndDate)
        then @NewEndDate
    when (@EndDate>@NewEndDate and @Startdate > @NewEndDate)
        then @NewEndDate
    when (@EndDate<@NewEndDate and @NewStartDate > @EndDate)
        then @NewEndDate
    else @EndDate end) as EndDate

Distrubution logic