Question Déterminer si deux plages de dates se chevauchent


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

A titre d'exemple, supposons que nous ayons des plages dénotées par des variables DateTime StartDate1 à EndDate1  et  StartDate2 à EndDate2.


984
2017-11-28 14:48


origine


Réponses:


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

Preuve:
Let ConditionA signifie que DateRange A complètement après DateRange B
_ |---- DateRange A ------| |---Date Range B -----| _
  (Vrai si StartA > EndB)

Soit ConditionB signifie que DateRange A est complètement antérieure à DateRange B
|---- DateRange A -----| _ _ |---Date Range B ----|
 (Vrai si EndA < StartB)

Alors Overlap existe si ni A Nor B est vrai -
 (Si une plage n'est pas 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 ça:

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

Ce qui signifie: (StartA <= EndB) and (EndA >= StartB)


REMARQUE: cela inclut les conditions où les bords se chevauchent exactement. Si vous souhaitez exclure cela,
changer la >= opérateurs à >, et <=  à < 


NOTE 2. Merci à @Baodad, voir ce blog, le chevauchement réel est le moindre de:
  { endA-startA, endA - startB, endB-startA, endB - startB }

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


NOTE 3. Grâce à @tomosius, une version plus courte se lit comme suit:
DateRangesOverlap = max(start1, start2) < min(end1, end2)
C'est en fait un raccourci syntaxique pour ce qui est une implémentation plus longue, qui inclut des vérifications supplémentaires pour vérifier que les dates de début sont sur ou avant les endDates. Dérivant cela d'en haut:

Si les dates de début et de fin peuvent être hors service, c'est-à-dire s'il est possible que startA > endA ou startB > endB, alors vous devez également vérifier qu'ils sont en 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() et Max(), vous devez coder, (en utilisant C ternary pour la finesse) ,:
(StartA > StartB? Start A: StartB) <= (EndA < EndB? EndA: EndB) 


1869
2017-11-28 15:00



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

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

320
2017-11-28 14:49



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

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

enter image description here


87
2018-04-08 22:42



Pour raisonner sur les relations temporelles (ou toute autre relation d'intervalle, venir à cela), considérez L'algèbre à intervalle d'Allen. Il décrit les 13 relations possibles que deux intervalles peuvent avoir les uns par rapport aux autres. 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 Snodgrass Développement d'applications orientées temps dans SQL (PDF disponible en ligne sur URL), et dans Date, Darwen et Lorentzos Données temporelles et modèle relationnel (2002) ou Théorie temporelle et relationnelle: bases de données temporelles dans le modèle relationnel et SQL (2014, effectivement la deuxième édition de TD & RM).


La réponse courte (ish) est: donné deux intervalles de date A et B avec des composants .start et .end et la contrainte .start <= .end, puis deux intervalles se chevauchent si:

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

Vous pouvez régler l'utilisation de >= contre > et <= contre < pour répondre à vos exigences de degré de chevauchement.


ErikE commente:

Vous ne pouvez obtenir que 13 si vous comptez des choses drôles ... Je peux obtenir "15 relations possibles que deux intervalles peuvent avoir" quand je deviens fou avec elle. Par un compte sensé, je n'en ai que six, et si vous vous souciez de savoir si A ou B vient en premier, je n'en ai que trois (pas d'intersection, d'intersection partielle, une entièrement dans l'autre). 15 va comme ceci: [avant: avant, début, dedans, fin, après], [début: début, dedans, fin, après], [dedans: dedans, fin, après], [fin: fin, après], [ après: après].

Je pense que vous ne pouvez pas compter les deux entrées avant: avant et après: après. Je pourrais voir 7 entrées si vous assimilez quelques 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, avec des égaux n'ayant pas un inverse distinct). Et si trois est sensible dépend de vos besoins.

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

66
2017-11-30 06:54



Si le chevauchement lui-même doit également être calculé, vous pouvez utiliser la formule suivante:

overlap = max(0, min(EndDate1, EndDate2) - max(StartDate1, StartDate2))
if (overlap > 0) { 
    ...
}

25
2017-09-06 02:07



Toutes les solutions qui vérifient une multitude de conditions en fonction de l'emplacement des plages les unes par rapport aux autres peuvent être grandement simplifiées juste en vous assurant qu'une gamme spécifique commence plus tôt! Vous vous assurez que la première plage commence plus tôt (ou en même temps) en inversant les plages si nécessaire à l'avance.

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

En supposant inclusives aux deux extrémités, il n'y a que quatre possibilités dont une est un chevauchement:

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

L'extrémité de la plage 2 n'y entre pas. 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:

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

Si les plages sont inclusives au départ et exclusives à la fin, il vous suffit de remplacer > avec >= dans la seconde if déclaration (pour le premier segment de code: dans le second segment de code, vous utiliseriez < 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 que vous devez effectuer car vous supprimez la moitié de l'espace problème en vous assurant que la plage 1 ne démarre jamais après la plage 2.


16
2017-08-06 02:39



Voici une autre solution utilisant JavaScript. Spécialités de ma solution:

  • Gère les valeurs nulles comme l'infini
  • Suppose que la borne inférieure est inclusive et la limite supérieure exclusive.
  • Livré avec un tas de tests

Les tests sont basés sur des entiers, mais comme les objets de date dans JavaScript sont comparables, vous pouvez simplement ajouter deux objets de date. Ou vous pouvez lancer l'horodatage à la milliseconde.

Code:

/**
 * Compares to comparable objects to find out whether they overlap.
 * It is assumed that the interval is in the format [from,to) (read: from is inclusive, to is exclusive).
 * A null value is interpreted as infinity
 */
function intervalsOverlap(from1, to1, from2, to2) {
    return (to2 === null || from1 < to2) && (to1 === null || to1 > from2);
}

Tests:

describe('', function() {
    function generateTest(firstRange, secondRange, expected) {
        it(JSON.stringify(firstRange) + ' and ' + JSON.stringify(secondRange), function() {
            expect(intervalsOverlap(firstRange[0], firstRange[1], secondRange[0], secondRange[1])).toBe(expected);
        });
    }

    describe('no overlap (touching ends)', function() {
        generateTest([10,20], [20,30], false);
        generateTest([20,30], [10,20], false);

        generateTest([10,20], [20,null], false);
        generateTest([20,null], [10,20], false);

        generateTest([null,20], [20,30], false);
        generateTest([20,30], [null,20], false);
    });

    describe('do overlap (one end overlaps)', function() {
        generateTest([10,20], [19,30], true);
        generateTest([19,30], [10,20], true);

        generateTest([10,20], [null,30], true);
        generateTest([10,20], [19,null], true);
        generateTest([null,30], [10,20], true);
        generateTest([19,null], [10,20], true);
    });

    describe('do overlap (one range included in other range)', function() {
        generateTest([10,40], [20,30], true);
        generateTest([20,30], [10,40], true);

        generateTest([10,40], [null,null], true);
        generateTest([null,null], [10,40], true);
    });

    describe('do overlap (both ranges equal)', function() {
        generateTest([10,20], [10,20], true);

        generateTest([null,20], [null,20], true);
        generateTest([10,null], [10,null], true);
        generateTest([null,null], [null,null], true);
    });
});

Résultat lors de l'exécution avec karma & jasmine & PhantomJS:

PhantomJS 1.9.8 (Linux): Exécuté 20 sur 20 SUCCÈS (0,003 secondes / 0,004 secondes)


12
2018-03-13 13:19



Je sais que cela a été étiqueté comme agnostique, mais pour vous tous en Java: ne pas réinventer la roue et utiliser Joda Time.

http://joda-time.sourceforge.net/api-release/org/joda/time/base/AbstractInterval.html#overlaps(org.joda.time.ReadableInterval)


8
2017-10-13 15:10



je ferais

StartDate1.IsBetween(StartDate2, EndDate2) || EndDate1.IsBetween(StartDate2, EndDate2)

IsBetween est quelque chose comme

    public static bool IsBetween(this DateTime value, DateTime left, DateTime right) {
        return (value > left && value < right) || (value < left && value > right);
    }

7
2017-11-28 14:51