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?

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

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

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

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

Solution 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

View more solutions