Bestimmen Sie, ob sich zwei Datumsbereiche überschneiden.

Question

Angenommen, wir haben Bereiche, die durch DateTime-Variablen StartDate1 bis EndDate1 und StartDate2 bis EndDate2 bezeichnet sind.

Answer 1

Alle Lösungen, die eine Vielzahl von Bedingungen überprüfen, basierend darauf, wo die Bereiche zueinander stehen, können erheblich vereinfacht werden, indem einfach sichergestellt wird, dass ein Bereich vor oder gleichzeitig wie der andere beginnt. Dies können Sie durch den Austausch der Bereiche vorab erreichen.

Dann können Sie eine Überlappung erkennen, wenn der Start des zweiten Bereichs:

• kleiner oder gleich dem Ende des ersten Bereichs ist (wenn die Bereiche inklusiv sind und sowohl die Start- als auch die Endzeiten enthalten); oder
• kleiner ist (wenn die Bereiche den Start einschließen und das Ende ausschließen).

Zum Beispiel (vorausgesetzt, sowohl am Anfang als auch am Ende inklusiv), gibt es nur vier Möglichkeiten für Bereich 2, von denen eine keine Überlappung darstellt (das > am Ende des Bereichs bedeutet, dass es nicht darauf ankommt, wo der Bereich endet):

|-----|        Bereich 1, die Zeilen unten sind alle Bereich 2.
|-->  :        Überlappung.
 |--> :        Überlappung.
      |--->    Überlappung (keine Überlappung im Fall von ausschließendem Ende).
       |--->   keine Überlappung.

Der Endpunkt des zweiten Bereichs beeinflusst das Ergebnis überhaupt nicht. Daher können Sie in Pseudocode etwas Ähnliches tun (vorausgesetzt, dass s <= e für alle Bereiche gilt - wenn nicht, müssen Sie sie auch austauschen):

def überschneidet_sich(r1, r2):
    if r1.s > r2.s:
        tausche r1, r2
    return r2.s <= r1.e

Oder die Option mit einer Rekursionsebene:

def überschneidet_sich(r1, r2):
    if r1.s <= r2.s:
        return r2.s <= r1.e
    return überschneidet_sich(r2, r1)

Wenn die Bereiche am Ende ausschließend sind, müssen Sie nur <= durch < im Ausdruck, den Sie zurückgeben, ersetzen (in beiden Code-Schnipseln).

Dies beschränkt die Anzahl der Überprüfungen erheblich, die Sie durchführen müssen, da Sie bereits früh die Hälfte des Problems entfernen, indem Sie sicherstellen, dass der erste Bereich niemals nach dem zweiten beginnt.

---

Und da "Code spricht", hier ist etwas Python-Code, der dies in Aktion zeigt, mit einer ziemlichen Anzahl von Testfällen. Zuerst die InclusiveRange-Klasse:

class InclusiveRange:
    """Klasse InclusiveRange zur Darstellung einer unteren und oberen Grenze."""

    def __init__(self, start, end):
        """Initialisierung, stellt sicher, dass start <= end.
        Args:
            start: Der Start des Bereichs.
            end: Das Ende des Bereichs.
        """
        self.start = min(start, end)
        self.end = max(start, end)

    def __repr__(self):
        """Rückgabe der Darstellung für f-String."""
        return f"({self.start}, {self.end})"

    def überschneidet_sich(self, other):
        """True, wenn Bereich mit einem anderen überlappt.
        Args:
            other: Der andere InclusiveRange, gegen den überprüft wird.
        """

        # Sehr begrenzte Rekursion, um sicherzustellen, dass der Start des ersten Bereichs
        # nicht nach dem Start des zweiten Bereichs liegt.

        if self.start > other.start:
            return other.überschneidet_sich(self)

        # Sehr vereinfachte Überprüfung der Überlappung.

        return other.start <= self.end

Dann ein Testfall-Handler, damit wir das Ergebnis eines einzigen Testfalls schön präsentieren können:

def test_fall(range1, range2):
    """Prüfung eines einzelnen Testfalls."""

    # Niedrigsten und höchsten Wert für "grafische" Ausgabe erhalten.

    low = min(range1.start, range2.start)
    high = max(range1.end, range2.end)

    # Ausgabe der Bereiche und der Grafik.

    print(f"r1={range1} r2={range2}: ", end="")
    for val in range(low, high + 1):
        is_in_first = range1.start <= val <= range1.end
        is_in_second = range2.start <= val <= range2.end

        if is_in_first and is_in_second:
            print("|", end="")
        elif is_in_first:
            print("'", end="")
        elif is_in_second:
            print(",", end="")
        else:
            print(" ", end="")

    # Schließlich Ausgabe des Ergebnisses der Überlappungsprüfung.

    print(f" - {range1.überschneidet_sich(range2)}\n")

Und schließlich eine anständige Anzahl von Testfällen, zu denen Sie bei Bedarf weitere hinzufügen können:

# Verschiedene Testfälle, fügen Sie weitere hinzu, wenn Sie die Richtigkeit anzweifeln.

test_fall(InclusiveRange(0, 1), InclusiveRange(8, 9))
test_fall(InclusiveRange(0, 4), InclusiveRange(5, 9))
test_fall(InclusiveRange(0, 4), InclusiveRange(4, 9))
test_fall(InclusiveRange(0, 7), InclusiveRange(2, 9))
test_fall(InclusiveRange(0, 4), InclusiveRange(0, 9))
test_fall(InclusiveRange(0, 9), InclusiveRange(0, 9))
test_fall(InclusiveRange(0, 9), InclusiveRange(4, 5))

test_fall(InclusiveRange(8, 9), InclusiveRange(0, 1))
test_fall(InclusiveRange(5, 9), InclusiveRange(0, 4))
test_fall(InclusiveRange(4, 9), InclusiveRange(0, 4))
test_fall(InclusiveRange(2, 9), InclusiveRange(0, 7))
test_fall(InclusiveRange(0, 9), InclusiveRange(0, 4))
test_fall(InclusiveRange(0, 9), InclusiveRange(0, 9))
test_fall(InclusiveRange(4, 5), InclusiveRange(0, 9))

Beim Ausführen wird die Ausgabe produziert:

r1=(0, 1) r2=(8, 9): ''      ,, - False
r1=(0, 4) r2=(5, 9): ''''',,,,, - False
r1=(0, 4) r2=(4, 9): ''''|,,,,, - True
r1=(0, 7) r2=(2, 9): ''||||||,, - True
r1=(0, 4) r2=(0, 9): |||||,,,,, - True
r1=(0, 9) r2=(0, 9): |||||||||| - True
r1=(0, 9) r2=(4, 5): ''''||'''' - True
r1=(8, 9) r2=(0, 1): ,,      '' - False
r1=(5, 9) r2=(0, 4): ,,,,,''''' - False
r1=(4, 9) r2=(0, 4): ,,,,|''''' - True
r1=(2, 9) r2=(0, 7): ,,||||||'' - True
r1=(0, 9) r2=(0, 4): |||||''''' - True
r1=(0, 9) r2=(0, 9): |||||||||| - True
r1=(4, 5) r2=(0, 9): ,,,,||,,,, - True

wo jede Zeile hat:

• die beiden bewerteten Bereiche;
• eine grafische Darstellung des "Bereichsraums" (vom niedrigsten Start bis zum höchsten Ende), bei der jedes Zeichen einen Wert in diesem "Bereichsraum" darstellt:
  • ' zeigt einen Wert nur im ersten Bereich an;
  • , zeigt einen Wert nur im zweiten Bereich an;
  • | zeigt einen Wert in beiden Bereichen an; und
  • zeigt einen Wert in keinem der Bereiche an.
• das Ergebnis der Überlappungsprüfung.

Es ist deutlich zu erkennen, dass Sie nur bei der Überlappungsprüfung true erhalten, wenn es mindestens einen Wert in beiden Bereichen gibt (d. h. ein | Zeichen). In allen anderen Fällen wird false zurückgegeben.

Fühlen Sie sich frei, weitere Werte hinzuzufügen, wenn Sie weitere Testfälle hinzufügen möchten.

Answer 2

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

• Verarbeitet Nullwerte als Unendlichkeit
• Geht davon aus, dass die untere Grenze inklusive und die obere Grenze exklusive ist.
• Beinhaltet eine Reihe von Tests

Die Tests basieren auf ganzen Zahlen, aber da Datumsobjekte in JavaScript vergleichbar sind, können Sie auch einfach zwei Datumsobjekte einwerfen. Oder Sie könnten den Millisekunden-Zeitstempel einwerfen.

Code:

/**
 * Vergleicht zwei vergleichbare Objekte, um festzustellen, ob sie sich überschneiden.
 * Es wird davon ausgegangen, dass das Intervall im Format [von,bis) (lesen: von ist inklusiv, bis ist exklusiv) ist.
 * Ein Nullwert wird als Unendlichkeit interpretiert
 */
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) + ' und ' + JSON.stringify(secondRange), function() {
            expect(intervalsOverlap(firstRange[0], firstRange[1], secondRange[0], secondRange[1])).toBe(expected);
        });
    }

    describe('Keine Überschneidung (Berühren der Enden)', 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('Überschneidung (ein Ende überschneidet sich)', 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('Überschneidung (ein Bereich im anderen Bereich enthalten)', 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('Überschneidung (beide Bereiche gleich)', 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 beim Ausführen mit Karma&Jasmine&PhantomJS:

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

Answer 3

Hier ist der Code, der die Zauberei macht:

 var isOverlapping =  ((A == null || D == null || A <= D) 
            && (C == null || B == null || C <= B)
            && (A == null || B == null || A <= B)
            && (C == null || D == null || C <= D));

Wo..

• A -> 1Start
• B -> 1End
• C -> 2Start
• D -> 2End

Beweis? Schauen Sie sich diesen Test Konsolen-Code-Gist an.

Answer 4

Ein einfacher Weg, um sich an die Lösung zu erinnern, wäre
min(Enden) > max(Starts)

Answer 5

Hier ist meine Lösung in Java, die auch auf unbeschränkte Intervalle funktioniert

private Boolean overlap (Timestamp startA, Timestamp endA,
                         Timestamp startB, Timestamp endB)
{
    return (endB == null || startA == null || !startA.after(endB))
        && (endA == null || startB == null || !endA.before(startB));
}