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) se chevauche avec une autre(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:
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 < tStartA && tEndB > tEndA //For case 3
(Le cas 4 est pris en compte dans le cas 1 ou le cas 2)
Il œuvres , mais il ne semble pas très efficace.
donc, d'abord il y a une classe existante en c# qui peut modéliser ceci(une période de temps), quelque chose comme un intervalle de temps, mais avec une date de début fixe.
Deuxièmement: y a-t-il déjà une C # code (comme dans la classe DateTime
) qui peut gérer cela?
Tiers: si non, quelle serait votre approche pour faire cette comparaison la plus rapide?
12 réponses
Simple de vérifier pour voir si les 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 changez d'avis sur le fait de vouloir dire que deux périodes qui se touchent juste se chevauchent.)
il y a une bibliothèque merveilleuse avec de bonnes critiques sur le projet de code: http://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET
Cette bibliothèque est beaucoup de travail concernant les chevauchements, d'intersection, etc. C'est trop gros copier/coller de tout cela, mais je vais voir parties spécifiques qui peuvent être utiles pour vous.
vous pouvez créer une classe réutilisable de motif de gamme:
public class Range<T> 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<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; } }
}
vous pouvez ajouter toutes les méthodes dont vous avez besoin pour fusionner les gammes, obtenir des intersections et ainsi de suite...
je construis un système de réservation et j'ai trouvé cette page. Je ne m'intéresse qu'à l'intersection des distances, donc j'ai construit cette structure; elle est suffisante pour jouer avec les distances de DateTime.
vous pouvez vérifier Intersection et vérifier si une date spécifique est à portée, et obtenir le type d'intersection et le plus important: vous pouvez obtenir la gamme intersected.
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,
}
Que Diriez-vous d'une structure personnalisée arbre des intervalles ? Vous devrez ruser un peu pour définir ce que cela signifie pour les deux intervalles de "chevauchement" dans votre domaine.
cette question pourrait vous aider à trouver une application standard de l'arborescence des intervalles dans C#.
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 se superpose pas avec 12: 30 13: 00
Je ne crois pas que le cadre lui-même ait cette classe. Peut-être une bibliothèque tierce...
mais pourquoi ne pas créer une classe valeur-objet de période pour gérer cette complexité? De cette façon, vous pouvez vous assurer d'autres contraintes, comme la validation des datetimes de début vs 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) { }
}
}
ainsi vous pourrez comparer individuellement chaque période...
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.
Note Startdatett and Enddatett are dateTime types""
--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
essayez ceci. Cette méthode va déterminer si (deux) les travées de date se chevauchent, indépendamment de l'ordre des arguments d'entrée de la méthode. Cette méthode peut également être utilisée pour plus de deux travées de datation, en vérifiant individuellement chaque combinaison de travées de datation (p. ex. avec 3 portées de date, exécuter span1
contre span2
, span2
contre span3
, et span1
contre span3
):
public static class HelperFunctions
{
public static bool AreSpansOverlapping(Tuple<DateTime,DateTime> span1, Tuple<DateTime,DateTime> 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<DateTime, DateTime>(span1.Item2, span1.Item1);
}
if (span2.Item1 > span2.Item2)
{
span2 = new Tuple<DateTime, DateTime>(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<DateTime, DateTime>(d1, d2),
new Tuple<DateTime, DateTime>(d3, d4),
true //or use False, to ignore span's endpoints
).ToString());
Console.WriteLine();
}
Console.WriteLine("COMPLETE");
System.Console.ReadKey();
}
C'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));
}
unité I testé avec une couverture de 100%.
@Dushan Gajik, vous semblez avoir un bug dans votre dernière affaire - il devrait être faux.
xxxxxxxxxxxxxxxxxxxxxxxxx
---|---|
--------|---|
TRUE
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;
}