Algoritmo para detectar períodos sobrepostos

Eu tenho que detectar se dois períodos de tempo estão sobrepostos.
Cada período tem uma data de início e uma data final.
Preciso detectar se meu primeiro período de tempo (A) está se sobrepondo a outro (B / C).
No meu caso, se o início de B é igual ao final de A, eles não estão sobrepostos (o inverso também)
Eu encontrei os seguintes casos:

insira a descrição da imagem aqui

Então, na verdade, estou fazendo assim:

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

(O caso 4 é levado na conta no caso 1 ou no caso 2)

Funciona , mas não parece muito eficiente.

Então, primeiro existe uma class existente em c # que pode modelar isso (um período de tempo), algo como um intervalo de tempo, mas com uma data de início fixa.

Segundo: já existe um código AC # (como na class DateTime ) que pode lidar com isso?

Terceiro: se não, qual seria a sua abordagem para tornar essa comparação mais rápida?

Verificação simples para ver se dois períodos de tempo se sobrepõem:

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

ou no seu código:

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

(Use < = invés de < se você mudar de idéia sobre querer dizer que dois períodos que apenas tocam um sobre o outro.)

Há uma biblioteca maravilhosa com boas críticas no CodeProject: http://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET

Essa biblioteca faz muito trabalho no que diz respeito à sobreposição, intersectando-os, etc. É muito grande para copiar / colar tudo isso, mas vou ver quais partes específicas podem ser úteis para você.

Você pode criar uma class de padrão de intervalo reutilizável:

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

Você pode adicionar todos os methods que você precisa para mesclar intervalos, obter interseções e assim por diante ...

Estou construindo um sistema de reservas e encontrei esta página. Estou interessado apenas na interseção de alcance, então construí essa estrutura; é o suficiente para jogar com intervalos de DateTime.

Você pode verificar Intersection e verificar se uma data específica está no intervalo e obter o tipo de interseção e o mais importante: você pode obter Intervalo interceptado.

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

Como sobre uma estrutura de tree de intervalo personalizada? Você terá que ajustar um pouco para definir o que significa dois “sobrepor” no seu domínio.

Essa questão pode ajudá-lo a encontrar uma implementação de tree de intervalo pronta para uso em C #.

Eu não acredito que o framework em si tenha essa class. Talvez uma biblioteca de terceiros …

Mas por que não criar uma class de object de valor Período para lidar com essa complexidade? Dessa forma, você pode garantir outras restrições, como validar datas de início e término. 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) { } } } 

Dessa forma, você poderá comparar individualmente cada período ...

Este código verifica se dois intervalos se sobrepõem.

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

exemplo 12:00 – 12:30 não está sobreposto às 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 distribuição

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

Obrigado pelas respostas acima que me ajudam a codificar o acima para um projeto MVC.

Nota StartDateDT e EndDateDT são tipos dateTime

Tente isso. Esse método determinará se (dois) períodos de datas estão sobrepostos, independentemente da ordem dos argumentos de input do método. Isso também pode ser usado com mais de dois períodos de data, verificando individualmente cada combinação de período (ex. Com 3 períodos de datas, entre span1 contra span2 , span2 contra span3 e 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 )); } } } } 

Teste:

 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 é minha solução:

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

Eu testei a unidade com 100% de cobertura.

@Dushan Gajik, você parece ter um bug no seu último caso - deve ser falso.

xxxxxxxxxxxxxxxxxxxxxxxxx

--- | --- |

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

VERDADE

Verifique este método simples (recomenda-se colocar este método em sua dateUtility

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