Algorithme pour détecter les périodes de chevauchement

Je dois détecter si deux périodes se chevauchent.
Chaque période a une date de début et une date de fin.
Je dois détecter si ma première période (A) chevauche une autre période (B / C).
Dans mon cas, si le début de B est égal à la fin de A, ils ne se chevauchent pas (l’inverse aussi)
J’ai trouvé les cas suivants:

entrer la description de l'image ici

Donc en fait je fais ça comme ça:

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

(Le cas 4 est pris dans le compte soit dans le cas 1 ou dans le cas 2)

Ça marche , mais ça semble pas très efficace.

Donc, d’abord, existe-t-il une classe existante dans c # qui peut modéliser cela (une période), quelque chose comme une période, mais avec une date de début fixe.

Deuxièmement: Y a-t-il déjà un code AC (comme dans la classe DateTime ) qui peut gérer cela?

Troisièmement: si non, quelle serait votre approche pour que cette comparaison soit la plus rapide?

Vérification simple pour voir si deux périodes se chevauchent:

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

ou dans votre code:

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

(Utilisez <= au lieu de < si vous ne voulez pas dire que deux périodes qui se touchent se chevauchent.)

Il existe une magnifique bibliothèque avec de bonnes critiques sur CodeProject: http://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET

Cette bibliothèque fait beaucoup de travail en ce qui concerne le chevauchement, leur intersection, etc. C’est trop gros pour tout copier / coller, mais je vais voir quelles parties spécifiques peuvent vous être utiles.

Vous pouvez créer une classe de modèle de plage réutilisable:

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

Vous pouvez append toutes les méthodes dont vous avez besoin pour fusionner des plages, obtenir des intersections, etc.

Je construis un système de réservation et trouve cette page. Je ne suis intéressé que par l’intersection des distances, j’ai donc construit cette structure. il suffit de jouer avec les gammes DateTime.

Vous pouvez vérifier l’intersection et vérifier si une date spécifique est dans la plage, et obtenir le type d’intersection et le plus important: vous pouvez obtenir une plage intersectée.

 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’en est-il d’une structure d’ arborescence d’intervalles personnalisée? Vous devrez le modifier un peu pour définir ce que cela signifie pour deux intervalles de “chevauchement” dans votre domaine.

Cette question pourrait vous aider à trouver une implémentation par intervalle standard dans C #.

Je ne crois pas que le framework lui-même a cette classe. Peut-être une bibliothèque tierce …

Mais pourquoi ne pas créer une classe d’object de valeur Période pour gérer cette complexité? De cette façon, vous pouvez garantir d’autres contraintes, telles que la validation des dates de début et de fin. Quelque chose comme:

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

Vous pourrez ainsi comparer individuellement chaque période ...

Ce code vérifie si deux intervalles se chevauchent.

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

Algorithme:

 x1 < y2 and x2 > y1 

exemple 12:00 – 12:30 ne fait pas double emploi avec 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 

Logique de distrubution

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

Merci pour les réponses ci-dessus qui m'aident à coder ce qui précède pour un projet MVC.

Remarque StartDateDT et EndDateDT sont des types dateTime

Essaye ça. Cette méthode déterminera si (deux) les plages de dates se chevauchent, quel que soit l’ordre de classement des arguments d’entrée de la méthode. Cela peut également être utilisé avec plus de deux intervalles de temps, en vérifiant individuellement chaque combinaison de période (ex. Avec 3 span1 temps, exécuter span1 contre span2 , span2 contre span3 et span1 contre 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 )); } } } } 

Tester:

 static void Main(ssortingng[] 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 ).ToSsortingng()); Console.WriteLine(); } Console.WriteLine("COMPLETE"); System.Console.ReadKey(); } 

Ceci est ma solution:

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

Je l'ai testé avec une couverture de 100%.

@Dushan Gajik, vous semblez avoir un bug dans votre dernier cas - ce serait faux.

xxxxxxxxxxxxxxxxxxxxxxxxx

--- | --- |

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

VRAI

Vérifiez cette méthode simple (il est recommandé de mettre cette méthode dans votre dateUtility

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