Algoritmo para detectar períodos superpuestos

Debo detectar si dos períodos de tiempo se superponen.
Cada período tiene una fecha de inicio y una fecha de finalización.
Necesito detectar si mi primer período de tiempo (A) se superpone con otro (B / C).
En mi caso, si el inicio de B es igual al final de A, no se solapan (el inverso también)
Encontré los siguientes casos:

enter image description here

Así que en realidad estoy haciendo esto así:

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

(El caso 4 se toma en la cuenta en el caso 1 o en el caso 2)

Funciona , pero parece no ser muy eficiente.

Entonces, primero hay una clase existente en c # que puede modelar esto (un período de tiempo), algo así como un intervalo de tiempo, pero con una fecha de inicio fija.

En segundo lugar: ¿Ya hay código de CA (como en la clase DateTime ) que puede manejar esto?

Tercero: si no, ¿cuál sería su enfoque para hacer que esta comparación sea la más rápida?

Verificación simple para ver si dos períodos de tiempo se superponen:

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

o en tu código:

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

(Use <= lugar de < si cambia de opinión acerca de querer decir que dos períodos que solo se tocan entre sí se superponen).

Hay una biblioteca maravillosa con buenas críticas en CodeProject: http://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET

Esa biblioteca hace mucho trabajo en cuanto a superposición, intersección, etc. Es demasiado grande para copiar / pegar todo, pero veré qué partes específicas te pueden ser útiles.

Puede crear una clase de patrón de rango reutilizable:

 public class Range 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 other) { return Min.CompareTo(other.Max) < 0 && other.Min.CompareTo(Max) < 0; } public T Min { get { return min; } } public T Max { get { return max; } } } 

Puede agregar todos los métodos que necesita para combinar rangos, obtener intersecciones, etc.

Estoy construyendo un sistema de reserva y encontré esta página. Estoy interesado solo en la intersección de rangos, así que construí esta estructura; es suficiente para jugar con los rangos de DateTime.

Puede verificar Intersección y verificar si una fecha específica está dentro del rango, y obtener el tipo de intersección y la más importante: puede obtener el Rango intersectado.

 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 { ///  /// No Intersection ///  None = -1, ///  /// Given range ends inside the range ///  EndsInRange, ///  /// Given range starts inside the range ///  StartsInRange, ///  /// Both ranges are equaled ///  RangesEqauled, ///  /// Given range contained in the range ///  ContainedInRange, ///  /// Given range contains the range ///  ContainsRange, } 

¿Qué tal una estructura de árbol de intervalos personalizada? Tendrás que ajustarlo un poco para definir lo que significa que dos intervalos se “superpongan” en tu dominio.

Esta pregunta podría ayudarlo a encontrar una implementación de árbol de intervalos disponible en C #.

No creo que el marco en sí tenga esta clase. Tal vez una biblioteca de terceros …

¿Pero por qué no crear una clase de valor de objeto Period para manejar esta complejidad? De esta forma, puede garantizar otras restricciones, como la validación de fechas de inicio y finalización. Algo como:

 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) { } } } 

De esta forma, podrá comparar individualmente cada período ...

Este código verifica si dos intervalos se superponen.

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

Algoritmo:

 x1 < y2 and x2 > y1 

ejemplo 12:00 – 12:30 no se superpone con 12:30 13:00

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

Lógica de distribución

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

Gracias por las respuestas anteriores que me ayudan a codificar lo anterior para un proyecto de MVC.

Nota StartDateDT y EndDateDT son tipos de fecha y hora

Prueba esto. Este método determinará si (dos) intervalos de fechas se superponen, independientemente del orden de los argumentos de entrada del método. Esto también se puede usar con más de dos intervalos de fechas, al verificar individualmente cada combinación de intervalo de fechas (por ejemplo, con 3 intervalos de fechas, ejecutar span1 contra span2 , span2 contra span3 y span1 contra span3 ):

 public static class HelperFunctions { public static bool AreSpansOverlapping(Tuple span1, Tuple 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(span1.Item2, span1.Item1); } if (span2.Item1 > span2.Item2) { span2 = new Tuple(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 )); } } } } 

Prueba:

 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(d1, d2), new Tuple(d3, d4), true //or use False, to ignore span's endpoints ).ToString()); Console.WriteLine(); } Console.WriteLine("COMPLETE"); System.Console.ReadKey(); } 

Esta es mi solución:

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

La unidad lo probó con una cobertura del 100%.

@Dushan Gajik, parece que tienes errores en tu último caso, podría ser falso.

xxxxxxxxxxxxxxxxxxxxxxxxx

--- | --- |

-------- | --- |

CIERTO

Verifique este sencillo método (se recomienda poner este método en su dateUtility

 public static bool isOverlapDates(DateTime dtStartA, DateTime dtEndA, DateTime dtStartB, DateTime dtEndB) { return dtStartA < dtEndB && dtStartB < dtEndA; }