Frage Ermitteln, ob zwei Datumsbereiche überlappen


Bei zwei Datumsbereichen ist es am einfachsten oder am effizientesten festzustellen, ob sich die beiden Datumsbereiche überschneiden.

Nehmen wir zum Beispiel an, dass es Bereiche gibt, die mit DateTime-Variablen bezeichnet werden StartDate1 zu EndDate1  und  StartDate2 zu EndDate2.


984
2017-11-28 14:48


Ursprung


Antworten:


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

Beweis:
Lassen Sie ConditionA bedeuten, dass DateRange A vollständig nach DateRange B
_ |---- DateRange A ------| |---Date Range B -----| _
  (Wahr wenn StartA > EndB)

Lassen Sie ConditionB bedeuten, dass DateRange A vollständig vor DateRange B steht
|---- DateRange A -----| _ _ |---Date Range B ----|
 (Wahr wenn EndA < StartB)

Dann besteht Überlappung, wenn weder A noch B wahr ist -
 (Wenn eine Reihe nicht vollständig nach der anderen ist,
   noch ganz vor dem anderen,      dann müssen sie sich überlappen.)

Jetzt einer von De Morgans Gesetze sagt, dass:

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

Was bedeutet: (StartA <= EndB) and (EndA >= StartB)


HINWEIS: Dies schließt Bedingungen ein, bei denen die Kanten genau überlappen. Wenn Sie das ausschließen möchten,
ändere das >= Betreiber zu >, und <=  zu < 


ANMERKUNG 2. Dank @Baodad, siehe dieser BlogDie tatsächliche Überlappung ist die geringste von:
  { endA-startA, endA - startB, endB-startA, endB - startB }

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


NOTIZ 3. Dank @tomosius liest eine kürzere Version:
DateRangesOverlap = max(start1, start2) < min(end1, end2)
Dies ist eigentlich eine syntaktische Abkürzung für eine längere Implementierung, die zusätzliche Überprüfungen enthält, um zu überprüfen, ob sich die Startdaten an oder vor den Enddaten befinden. Ableiten von oben:

Wenn Anfangs- und Enddatum außerhalb der Reihenfolge liegen können, d. H. Wenn dies möglich ist startA > endA oder startB > endB, dann müssen Sie auch überprüfen, ob sie in Ordnung sind, das heißt, Sie müssen zwei zusätzliche Gültigkeitsregeln hinzufügen:
(StartA <= EndB) and (StartB <= EndA) and (StartA <= EndA) and (StartB <= EndB) oder:
(StartA <= EndB) and (StartA <= EndA) and (StartB <= EndA) and (StartB <= EndB) oder,
(StartA <= Min(EndA, EndB) and (StartB <= Min(EndA, EndB)) oder:
(Max(StartA, StartB) <= Min(EndA, EndB) 

Aber um zu implementieren Min() und Max(), Sie müssen code (mit C ternary für Kürze):
(StartA > StartB? Start A: StartB) <= (EndA < EndB? EndA: EndB) 


1869
2017-11-28 15:00



Ich glaube, es genügt zu sagen, dass sich die beiden Bereiche überlappen, wenn

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

320
2017-11-28 14:49



Dieser Artikel Zeitraumbibliothek für .NET beschreibt die Beziehung zweier Zeiträume durch die Aufzählung 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



Wenn Sie über zeitliche Beziehungen (oder irgendwelche anderen Intervallbeziehungen) nachdenken wollen, denken Sie darüber nach Allens Intervallalgebra. Es beschreibt die 13 möglichen Beziehungen, die zwei Intervalle zueinander haben können. Sie können andere Referenzen finden - "Allen Interval" scheint ein operativer Suchbegriff zu sein. Sie können auch Informationen über diese Vorgänge in Snodgrass finden Entwicklung von zeitorientierten Anwendungen in SQL (PDF verfügbar online unter URL), und in Date, Darwen und Lorentzos Zeitdaten und das relationale Modell (2002) oder Zeit- und Relationstheorie: Temporäre Datenbanken im relationalen Modell und SQL (2014; effektiv die zweite Ausgabe von TD & RM).


Die kurze (ish) Antwort ist: gegeben zwei Datumsintervalle A und B mit Komponenten .start und .end und die Beschränkung .start <= .end, dann überlappen sich zwei Intervalle, wenn:

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

Sie können die Verwendung von einstellen >= vs > und <= vs < um Ihre Anforderungen für den Grad der Überlappung zu erfüllen.


ErikE kommentiert:

Sie können nur 13 bekommen, wenn Sie die Dinge lustig zählen ... Ich kann "15 mögliche Beziehungen, die zwei Intervalle haben können" bekommen, wenn ich damit verrückt werde. Durch vernünftiges Zählen bekomme ich nur sechs, und wenn Sie sich kümmern, ob A oder B zuerst kommt, bekomme ich nur drei (kein Schnittpunkt, teilweise Schnittpunkt, einer ganz im anderen). 15 geht so: [vorher: vor, anfang, innerhalb, ende, nachher], [anfang: anfang, innerhalb, ende, nachher], [innerhalb: innerhalb, ende, nachher], [ende: ende, nachher], [ nach: nach].

Ich denke, dass man die zwei Einträge "vorher: vorher" und "danach: nachher" nicht zählen kann. Ich könnte 7 Einträge sehen, wenn Sie einige Relationen mit ihren Inversen gleichsetzen (siehe das Diagramm in der referenzierten Wikipedia-URL; es hat 7 Einträge, von denen 6 eine unterschiedliche Inverse haben, wobei equals keine eindeutige Inverse haben). Und ob drei sinnvoll sind, hängt von Ihren Anforderungen ab.

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

66
2017-11-30 06:54



Wenn die Überlappung selbst ebenfalls berechnet werden soll, können Sie die folgende Formel verwenden:

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

25
2017-09-06 02:07



Alle Lösungen, die eine Vielzahl von Bedingungen auf der Grundlage überprüfen, wo die Bereiche in Bezug zueinander stehen, können stark vereinfacht werden Nur dafür sorgen, dass ein bestimmter Bereich früher beginnt! Sie stellen sicher, dass der erste Bereich früher (oder zur gleichen Zeit) beginnt, indem Sie die Bereiche gegebenenfalls im Voraus austauschen.

Dann können Sie eine Überlappung erkennen, wenn der andere Bereichsbeginn kleiner oder gleich dem ersten Bereichsende ist (wenn die Bereiche inklusive sind und Start- und Endzeiten enthalten) oder kleiner als (wenn die Bereiche Start und Ende einschließen) .

Unter Annahme von inklusiv an beiden Enden gibt es nur vier Möglichkeiten, von denen eine eine Nicht-Überlappung ist:

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

Der Endpunkt des Bereichs 2 tritt nicht ein. Also, in Pseudocode:

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

Dies könnte noch mehr vereinfacht werden in:

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

Wenn die Bereiche am Anfang inklusive und am Ende exklusiv sind, müssen Sie nur ersetzen > mit >= in dieser Sekunde if Anweisung (für das erste Code-Segment: im zweiten Code-Segment würden Sie verwenden < eher, als <=):

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

Sie begrenzen die Anzahl der Prüfungen, die Sie vornehmen müssen, erheblich, da Sie die Hälfte des Problembereichs frühzeitig entfernen, indem Sie sicherstellen, dass Bereich 1 nach Bereich 2 nicht startet.


16
2017-08-06 02:39



Hier ist noch eine andere Lösung mit JavaScript. Besonderheiten meiner Lösung:

  • Verarbeitet Nullwerte als Unendlichkeit
  • Es wird davon ausgegangen, dass die untere Grenze einschließlich und die obere beschränkt ist.
  • Kommt mit einer Reihe von Tests

Die Tests basieren auf Ganzzahlen, aber da Datumsobjekte in JavaScript vergleichbar sind, können Sie auch zwei Datumsobjekte einfügen. Oder Sie könnten den Millisekunden-Zeitstempel einwerfen.

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

Ergebnis bei der Ausführung mit Karma & Jasmine & PhantomJS:

PhantomJS 1.9.8 (Linux): 20 von 20 Erfolgen durchgeführt (0,003 Sek. / 0,004 Sek.)


12
2018-03-13 13:19



Ich weiß, dass dies als sprachunabhängig gekennzeichnet wurde, aber für alle, die Sie in Java implementieren: Erfinden Sie das Rad nicht neu und verwenden Sie 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