Algorithm to detect overlapping periods [duplicate]

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?

Ganef

Period (C) in Case 5 is confusing me. Does this represent the non-overlapping situation(s)? If so wouldn't you split in two, Case 5 B wholly before A, Case 6 A wholly before B? – Diplomatics

yes its non-overlapping. – Ganef

There is a case 6 where the two date rages are identical -- the accepted answer does not give a correct answer for this case - If you're using this solution, you might want to think about updating your code!! – Centaur

@DanB Edit in fact no, If I check, I think the solution is covering the case: if a.start and b.start are equals and same for the end, you have: a.start < a.end && a.start < a.end which is true. – Ganef

Hi. I know its a bit late but what if I have a list of date ranges which is stored in database, How can I create a select statement which will identify if a user input date overlaps with my data in the database? – Discoloration

Merge Overlapping Intervals algorithm can give some leads. – Antirrhinum

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

Histopathology

Thank you for the very quick response! Excellent! seems to be very effective :) – Ganef

I don't see how this covers all scenarios. – Pagurian

@doker Feel free to demonstrate a scenario that it doesn't cover. – Histopathology

@Rawling. I see that it work but only if you do two checks. Check(a,b); Check(b,a); – Pagurian

@doker It's symmetrical. If you swap a and b you get the same statement, just with either side of the && switched. – Histopathology

Beautiful! It answers "could two people have met" with "yes if both were born before the other died". The reason this works becomes clear when you express the opposite: "no if either died before the other was born." In effect, testing for case 5 only: overlap = !(a.start > b.end || b.start > a.end) – Diplomatics

@doker Came up with another way to explain this astonishing simplification: notice that in cases 1-4 all the tStarts are less than all the tEnds. So there exists a time that is after all the tStarts and before all the tEnds. I.E. overlap. If you can assume each period orders itself correctly (its own tStart < tEnd), then the task reduces to "cross checking". – Diplomatics

An Issue with this solution is if the Start and Finish times are exactly the same. – Roehm

@Roehm How is that an issue? – Histopathology

@Histopathology If you are talking about a moment in time (or sometimes how full day events are stored with a flag also) with A having start and finish time of 12-Apr-2015 00:00. That does overlap with B with a start and finish time of 12-Apr-2015 00:00. But this would not detect it – Roehm

@Roehm That's not an issue with zero-length periods, that's an issue with periods that just touch rather than truly overlapping, which is addressed by my final paragraph in parentheses. – Histopathology

This doesn't work if the 2 date ranges are exactly the same.... can anyone verify... and it's not interchangeable... if you flip the 2 a and b, it does not work... If you used this code, you are not getting reliable answers from everything I can see)... – Centaur

@DanB If the two ranges are the same you get a.start < a.end && a.start < a.end which is trivially true. If you swap a and b you get b.start < a.end && a.start < b.end which just switches the arguments to the &&. – Histopathology

What difference would a not short-circuit AND operator have here? (&) – Fed

@Fed No difference to the result, but it may cause b.start and a.end to be evaluated in cases where the && operator would not. – Histopathology

I guess scenario that @Roehm bring up is still valid. created simple test check it's results.. gist(gist.github.com/sandeeptalabathula/…) – Agglutinogen

@sandeeptalabathula Again, if you want to count touching periods rather than a non-zero amount of overlap, just use <= instead of <. – Histopathology

I believe it does not work in all the cases. I have tried this logic to compare timespan objects in c# in case of 12 pm - 1:15 pm and 12:30 pn - 1:45 pm...this doesnt work – Bain

@Bain Well, you can work out whether 12pm < 1:45pm and 12:30pm < 1:15pm for yourself. – Histopathology

Great implementation but If there is a item completly out of the range it will not work correctly. Here are combinations to get rid of that. (b.StartTime <= a.StartTime && b.EndTime >= a.StartTime && b.EndTime <= a.EndTime) || (b.StartTime >= a.StartTime && b.EndTime <= a.EndTime) || (b.StartTime >= a.StartTime && b.StartTime <= a.EndTime && b.EndTime >= a.EndTime) – Fayefayette

@Fayefayette can you give an example it doesn't work on? – Histopathology

It will work for what the PO asked for, but if b is > a.start and end it would result with your solution as overlapping. – Fayefayette

@Fayefayette If b.start > a.end it will return false. – Histopathology

@Histopathology I dont see that in your solution – Fayefayette

@Fayefayette if b.start > a.end, b.start < a.end is false, so the && will be false. – Histopathology

For the above solution keep in mind that if a and b are equal, the result will be false. – Netsuke

Hi All, What about open ended time ranges? – Miguelinamiguelita

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.

Demodulation

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

Shyster

Good answer, however the comparison should be return Min.CompareTo(other.Max) <= 0 && other.Min.CompareTo(Max) <= 0; – Rachelrachele

code public bool InersectsW – Christology

how to inject this class using IoC like autofac? – Taveras

This implementation is immutable so you can inject it. And I suggest to not make it mutable. If you really want to inject it, declare an interface, implement a parameterless Ctor and make Min and Max properties mutable – Shyster

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,
}

Blim

Thank you very much for this implementation. It is a comprehensive implementation that had no issues. – Argentite

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

Experiment

In case 2, the first lower boundary is equal to the second upper boundary and it says FALSE which I take to mean, no overlap. However in the case of 10 the first upper boundary equals the second lower boundary and it says TRUE. These are not conceptually different unless there is some abstract meaning to the first and second members you haven't given. I think this invalidates that algorithm. – Gilud

@Gilud The algorithm is valid. That TRUE was probably just a typo. I have submitted an edit to this answer so the last 2 scenarios show FALSE as expected. – Vernievernier

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.

Childress

I think writing it like aStart < bStart && aStart < bEnd || aStart > bStart && aStart > bEnd makes it a little more clear because it clearly shows that any appointment that's earlier or later is valid. I don't think the truth table changes in this case. – Cureton

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

Saire

Answer 8

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;
        }

Crock

It has the advantage of a perfect code rather than a single line, for beginners it is very significant – Crock

well, for me it's about the algorithm, it's applicable in any language. – Ganef

Answer 9

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

Rhpositive

Try here codeproject.com/Articles/168662/Time-Period-Library-for-NET – Christology

Answer 10

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();
}

Tantalum

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

Christology

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

Helgeson

Not sure how you can consider this answer better than the one I accepted? – Ganef