Déterminer si deux plages de dates se chevauchent

Question

Étant donné deux plages de dates, quel est le moyen le plus simple ou le plus efficace de déterminer si les deux plages de dates se chevauchent ?

À titre d'exemple, supposons que nous ayons des plages désignées par des variables DateTime StartDate1 a EndDate1 y StartDate2 a EndDate2 .

Answer 1

(DébutA <= FinB) et (FinA >= DébutB)

Preuve :
Que la ConditionA signifie que la DateRange A est complètement après la DateRange B

_                        |---- DateRange A ------|
|---Date Range B -----|                          _

(Vrai si StartA > EndB )

La condition B signifie que la plage de dates A est complètement antérieure à la plage de dates B.

|---- DateRange A -----|                        _ 
_                          |---Date Range B ----|

(Vrai si EndA < StartB )

Alors le chevauchement existe si ni A ni B n'est vrai -
(Si une gamme n'est ni complètement après l'autre,
ni complètement avant l'autre, alors ils doivent se chevaucher).

Maintenant, l'un des Les lois de Morgan dit cela :

Not (A Or B) <=> Not A And Not B

Ce qui se traduit par : (StartA <= EndB) and (EndA >= StartB)

---

NOTE : Cela inclut les conditions où les bords se chevauchent exactement. Si vous souhaitez exclure cela,
changer le >= les opérateurs à > y <= à <

---

NOTE2. Merci à @Baodad, voir ce blog le chevauchement réel est le moins élevé des deux :
{ endA-startA , endA - startB , endB-startA , endB - startB }

(StartA <= EndB) and (EndA >= StartB) (StartA <= EndB) and (StartB <= EndA)

---

NOTE3. Grâce à @tomosius, une version plus courte se lit :
DateRangesOverlap = max(start1, start2) < min(end1, end2)
Il s'agit en fait d'un raccourci syntaxique pour une implémentation plus longue, qui comprend des contrôles supplémentaires pour vérifier que les dates de début sont égales ou antérieures aux dates de fin. Dérivant de ce qui précède :

Si les dates de début et de fin peuvent ne pas être dans l'ordre, c'est-à-dire s'il est possible que startA > endA o startB > endB il faut alors vérifier qu'ils sont dans l'ordre, ce qui signifie que vous devez ajouter deux règles de validité supplémentaires :
(StartA <= EndB) and (StartB <= EndA) and (StartA <= EndA) and (StartB <= EndB) ou :
(StartA <= EndB) and (StartA <= EndA) and (StartB <= EndA) and (StartB <= EndB) ou,
(StartA <= Min(EndA, EndB) and (StartB <= Min(EndA, EndB)) ou :
(Max(StartA, StartB) <= Min(EndA, EndB)

Mais pour mettre en œuvre Min() y Max() vous devez coder, (en utilisant le ternaire en C pour la tersité), :
(StartA > StartB? Start A: StartB) <= (EndA < EndB? EndA: EndB)

Answer 2

Je crois qu'il est suffisant de dire que les deux gammes se chevauchent si :

(StartDate1 <= EndDate2) and (StartDate2 <= EndDate1)

Answer 3

Cet article Bibliothèque de périodes de temps pour .NET décrit la relation de deux périodes de temps par l'énumération PériodeRelation :

// ------------------------------------------------------------------------
public enum PeriodRelation
{
    After,
    StartTouching,
    StartInside,
    InsideStartTouching,
    EnclosingStartTouching,
    Enclosing,
    EnclosingEndTouching,
    ExactMatch,
    Inside,
    InsideEndTouching,
    EndInside,
    EndTouching,
    Before,
} // enum PeriodRelation

Answer 4

Pour raisonner sur des relations temporelles (ou toute autre relation d'intervalle, d'ailleurs), on peut considérer L'algèbre d'intervalle d'Allen . Il décrit les 13 relations possibles que deux intervalles peuvent avoir l'un par rapport à l'autre. Vous pouvez trouver d'autres références - "Allen Interval" semble être un terme de recherche opérationnel. Vous pouvez également trouver des informations sur ces opérations dans l'ouvrage de Snodgrass intitulé Développer des applications orientées temps en SQL (PDF disponible en ligne à l'URL), et dans Date, Darwen et Lorentzos Les données temporelles et le modèle relationnel (2002) ou Le temps et la théorie relationnelle : Bases de données temporelles dans le modèle relationnel et SQL (2014 ; en fait la deuxième édition de TD&RM).

---

La réponse courte (ou presque) est la suivante : étant donné deux intervalles de dates A y B avec les composants .start y .end et la contrainte .start <= .end alors deux intervalles se chevauchent si :

A.end >= B.start AND A.start <= B.end

Vous pouvez régler l'utilisation de >= vs > y <= vs < pour répondre à vos exigences en matière de degré de chevauchement.

---

Commentaires d'ErikE :

Tu ne peux en obtenir que 13 si tu comptes les choses bizarrement... Je peux obtenir "15 relations possibles que deux intervalles peuvent avoir" quand je fais des folies avec ça. En comptant de manière sensée, je n'en obtiens que six, et si vous ne vous souciez pas de savoir si A ou B vient en premier, je n'en obtiens que trois (pas d'intersection, intersection partielle, l'un entièrement dans l'autre). 15 va comme ceci : [avant:avant, début, intérieur, fin, après], [début:début, intérieur, fin, après], [intérieur:intérieur, fin, après], [fin:fin, après], [après:après].

Je pense que vous ne pouvez pas compter les deux entrées 'before:before' et 'after:after'. Je pourrais voir 7 entrées si vous mettez en équation certaines relations avec leurs inverses (voir le diagramme dans l'URL Wikipedia référencée ; il a 7 entrées, dont 6 ont un inverse différent, les égaux n'ayant pas d'inverse distinct). Et si trois est raisonnable, cela dépend de vos besoins.

----------------------|-------A-------|----------------------
    |----B1----|
           |----B2----|
               |----B3----|
               |----------B4----------|
               |----------------B5----------------|
                      |----B6----|
----------------------|-------A-------|----------------------
                      |------B7-------|
                      |----------B8-----------|
                         |----B9----|
                         |----B10-----|
                         |--------B11--------|
                                      |----B12----|
                                         |----B13----|
----------------------|-------A-------|----------------------

Answer 5

Toutes les solutions qui consistent à vérifier une multitude de conditions en fonction de l'emplacement des plages les unes par rapport aux autres peuvent être grandement simplifiées par les moyens suivants il s'agit simplement de s'assurer qu'une gamme spécifique commence plus tôt ! Vous veillez à ce que la première série commence plus tôt (ou en même temps) en intervertissant les séries si nécessaire dès le départ.

Ensuite, vous pouvez détecter un chevauchement si le début de l'autre plage est inférieur ou égal à la fin de la première plage (si les plages sont inclusives, contenant à la fois les heures de début et de fin) ou inférieur à (si les plages sont inclusives du début et exclusives de la fin).

En supposant que les deux extrémités sont inclusives, il n'y a que quatre possibilités, dont l'une est un non-chevauchement :

|----------------------|        range 1
|--->                           range 2 overlap
 |--->                          range 2 overlap
                       |--->    range 2 overlap
                        |--->   range 2 no overlap

Le point final de l'intervalle 2 n'entre pas en ligne de compte. Donc, en pseudo-code :

def doesOverlap (r1, r2):
    if r1.s > r2.s:
        swap r1, r2
    if r2.s > r1.e:
        return false
    return true

Cela pourrait être simplifié encore plus en :

def doesOverlap (r1, r2):
    if r1.s > r2.s:
        swap r1, r2
    return r2.s <= r1.e

Si les plages sont inclusives au début et exclusives à la fin, il suffit de remplacer > con >= dans la seconde if (pour le premier segment de code : dans le deuxième segment de code, vous utiliserez l'instruction < plutôt que <= ):

|----------------------|        range 1
|--->                           range 2 overlap
 |--->                          range 2 overlap
                       |--->    range 2 no overlap
                        |--->   range 2 no overlap

Vous limitez considérablement le nombre de vérifications à effectuer car vous supprimez la moitié de l'espace du problème dès le début en vous assurant que la plage 1 ne commence jamais après la plage 2.