# Detection algorithm for overlapping periods [duplicate]

## Problem

I need to figure out if two time periods overlap. Each era has a beginning and an end date. I’m trying to figure out if my initial time period (A) overlaps with another (B/C). If the start of B equals the finish of A in my example, they are not overlapping (the inverse too) I discovered the following examples:

So here’s how I’m going about it:

``````tStartA < tStartB && tStartB < tEndA //For case 1
OR
tStartA < tEndB && tEndB <= tEndA //For case 2
OR
tStartB < tStartA  && tEndB > tEndA //For case 3
``````

(Case 4 is taken into consideration in either case 1 or case 2)

It appears to work, however it is inefficient.

So, first and foremost, is there a class in C# that can describe this (a time period), similar to a timespan but with a specified start date?

Second, is there already a c# function that can handle this (like in the DateTime class)?

Third, if no, how would you go about making this comparison as quickly as possible?

## Solution #1

To see if two time periods overlap, do the following:

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

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

(If you change your mind about wanting to state that two periods that just touch overlap, use = instead of.)

## Solution #2

On CodeProject, there is a fantastic library with excellent reviews: http://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET

That library does a lot of work with overlap, intersecting them, and other such things. It’s too large to copy/paste everything, but I’ll see what bits might be relevant to you.

## Solution #3

You can make a Range pattern class that you can reuse:

``````public class Range<T> where T : IComparable
{

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

To merge ranges, get intersections, and so on, you can add all the methods you need…

## Solution #4

I’m working on a booking system and came on this page. I designed this structure since I’m only interested in range intersection; it’s 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 determines if two intervals intersect.

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

12:00 – 12:30, for example, does not coincide with 12:30 13:00.