Algoritmo per rilevare periodi di sovrapposizione

Devo rilevare se due periodi di tempo si sovrappongono.
Ogni periodo ha una data di inizio e una data di fine.
Devo rilevare se il mio primo periodo di tempo (A) si sovrappone a un altro (B / C).
Nel mio caso, se l’inizio di B è uguale alla fine di A, non si sovrappongono (anche l’inverso)
Ho trovato i seguenti casi:

inserisci la descrizione dell'immagine qui

Quindi in realtà sto facendo questo in questo modo:

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

(Il caso 4 è preso nel conto nel caso 1 o nel caso 2)

Funziona , ma non sembra molto efficiente.

Quindi, prima c’è una class esistente in c # che può modellizzare questo (un periodo di tempo), qualcosa come un intervallo di tempo, ma con una data di inizio fissa.

Secondo: c’è già un codice # (come nella class DateTime ) che può gestire questo?

Terzo: se no, quale sarebbe il tuo approccio per rendere questo confronto il più veloce?

Controllo semplice per vedere se due periodi si sovrappongono:

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

o nel tuo codice:

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

(Usa <= invece di < se cambi idea sul voler dire che due periodi che si toccano l'un l'altro si sovrappongono).

C’è una meravigliosa libreria con buone recensioni su CodeProject: http://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET

Quella libreria fa un sacco di lavoro per sovrapporre, intersecarli, ecc. È troppo grande per copiarli / incollarli tutti, ma vedrò quali parti specifiche ti possono essere utili.

Puoi creare una class pattern Range riutilizzabile:

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

Puoi aggiungere tutti i metodi necessari per unire intervalli, ottenere intersezioni e così via ...

Sto costruendo un sistema di prenotazione e ho trovato questa pagina. Mi interessa solo l’intersezione della gamma, quindi ho costruito questa struttura; è sufficiente giocare con intervalli DateTime.

È ansible controllare l’intersezione e verificare se una data specifica è nell’intervallo e ottenere il tipo di intersezione e il più importante: è ansible ottenere l’intervallo intersecato.

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

Che ne dici di una struttura ad albero intervallo personalizzata? Dovrai modificarlo un po ‘per definire cosa significhi per due intervalli “sovrapporsi” al tuo dominio.

Questa domanda potrebbe aiutarti a trovare un’implementazione intervallo-albero pronta per l’uso in C #.

Non credo che lo stesso framework abbia questa class. Forse una libreria di terze parti …

Ma perché non creare una class object valore Periodo per gestire questa complessità? In questo modo puoi garantire altri vincoli, come la convalida dei tempi di inizio e fine. Qualcosa di simile a:

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

In questo modo sarai in grado di confrontare individualmente ciascun periodo ...

Questo codice controlla se due intervalli si sovrappongono.

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

l’esempio 12:00 – 12:30 non si sovrappone alle 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 

Logica di distrubuzione

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

Grazie per le risposte di cui sopra che mi aiutano a codificare quanto sopra per un progetto MVC.

Nota StartDateDT e EndDateDT sono tipi dateTime

Prova questo. Questo metodo determinerà se (due) intervalli di date si sovrappongono, indipendentemente dall’ordinamento degli argomenti di input del metodo. Questo può anche essere usato con più di due date, controllando individualmente ciascuna combinazione di date (ad esempio con 3 date span, esegui span1 contro span2 , span2 contro span3 e span1 contro 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 )); } } } } 

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

Questa è la mia soluzione:

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

L'unità l'ho testata con una copertura del 100%.

@Dushan Gajik, sembra che tu abbia un bug nel tuo ultimo caso - potrebbe essere falso.

xxxxxxxxxxxxxxxxxxxxxxxxx

--- | --- |

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

VERO

Controlla questo metodo semplice (si consiglia di inserire questo metodo nella dateUtility

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