Algorithme pour détecter les périodes qui se chevauchent

Question

Je dois détecter si deux périodes de temps 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 de temps (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 (et inversement)
J'ai trouvé les cas suivants :

Donc en réalité, je fais cela :

tStartA < tStartB && tStartB < tEndA //Pour le cas 1
OU
tStartA < tEndB && tEndB <= tEndA //Pour le cas 2
OU
tStartB < tStartA  && tEndB > tEndA //Pour le cas 3

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

Cela fonctionne, mais cela ne semble pas très efficace.

Alors, premièrement, y a-t-il une classe existante en c# qui peut modéliser ceci (une période de temps), quelque chose comme une timespan, mais avec une date de début fixe.

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

Troisièmement : si ce n'est pas le cas, quelle serait votre approche pour rendre cette comparaison la plus rapide possible?

Answer 1

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

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

ou dans votre code :

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

(Utilisez <= au lieu de < si vous changez d'avis et que vous voulez dire que deux périodes qui se touchent se chevauchent.)

Answer 2

Il y a une merveilleuse 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 concernant les chevauchements, les intersections, etc. Elle est trop volumineuse pour la copier/coller en entier, mais je vais voir quelles parties spécifiques peuvent vous être utiles.

Answer 3

Vous pouvez créer une classe de motif 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 ajouter toutes les méthodes dont vous avez besoin pour fusionner des plages, obtenir des intersections, etc...

Answer 4

Que diriez-vous d'une structure d'arbre d'intervalles personnalisée interval-tree ? Vous devrez le modifier un peu pour définir ce que signifie que deux intervalles "se chevauchent" dans votre domaine.

Cette question pourrait vous aider à trouver une implémentation d'arbre d'intervalles prête à l'emploi en C#.

Answer 5

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

Mais pourquoi ne pas créer une classe value-object Period pour gérer cette complexité? De cette façon, vous pouvez garantir d'autres contraintes, comme valider les datetimes 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) { }    
    }
}

De cette façon, vous pourrez comparer individuellement chaque période...