iOS-Terminkonflikte mit halboffenen Intervallen prüfen

In der Buchungsliste schließen zwei Besprechungen direkt aneinander an, doch beim Absenden wird ein Konflikt gemeldet. Ein anderer Eintrag umfasst drei kürzere Buchungen vollständig, während die Statistik nur eine gleichzeitige Belegung ausweist. Bei beiden Fehlern muss die Suche nicht in der Oberfläche beginnen. Auf einem Cloud-Mac lassen sich die Intervallfunktionen in reinem Swift isolieren und mit festgelegten Randbedingungen und Referenzergebnissen prüfen. So wird der Fehler auf reproduzierbare Eingaben eingegrenzt. Hier geht es um die Belegungszeiten einer einzelnen Ressource, nicht um die Datumsanzeige oder Netzwerkanfragen.

Zuerst den Vertrag für halboffene Intervalle festlegen

Jede Buchung wird als [start, end) dargestellt: Der Beginn gehört zum Intervall, das Ende nicht. Deshalb stehen [0, 10) und [10, 20) nicht im Konflikt, [0, 10) und [9, 20) dagegen schon. Als Zeiteinheit kommen Sekunden oder Minuten infrage. Innerhalb einer Berechnung muss die Einheit jedoch einheitlich sein; unterschiedliche Genauigkeiten dürfen nicht direkt vermischt werden.

Bereits am Eingang sind Werte abzulehnen, deren Ende nicht nach dem Beginn liegt. Eine Erinnerung ohne Dauer ist keine Belegungsbuchung und gehört in ein anderes Datenmodell. Fügen Sie nicht stillschweigend eine Sekunde hinzu, nur damit sie in die Sortierung passt.

Das „Zusammenführen belegter Zeiträume“ und die „maximale Anzahl gleichzeitiger Belegungen“ sind zwei verschiedene Aufgaben. Beim Zusammenführen geht die Anzahl der Überlagerungen verloren. Deshalb dürfen die Intervalle nicht erst zusammengeführt werden, bevor die Gleichzeitigkeit berechnet wird.

Verlangen die fachlichen Regeln eine Vorbereitungszeit zwischen zwei Besprechungen, muss diese zunächst in die Belegungsintervalle eingerechnet werden. Anschließend gelten dieselben Regeln. Eine zusätzliche Prüfung nur in der Oberfläche würde dazu führen, dass die Liste und die Schnittstelle zum Absenden unterschiedliche Antworten liefern.

Eine eigenständig ausführbare Kernimplementierung schreiben

Speichern Sie den folgenden Inhalt als Intervals.swift. Der Code verwendet ausschließlich die Standardbibliothek. Beim Zusammenführen verbindet er nur Intervalle, die sich tatsächlich überschneiden; direkt aneinandergrenzende Intervalle gelten nicht als überlappend. Ganzzahlige Zeitwerte dienen hier dazu, den Algorithmus zunächst von der Datumskonvertierung zu trennen.

typealias Slot = Range<Int>

func merged(_ input: [Slot]) -> [Slot] {
    precondition(input.allSatisfy { !$0.isEmpty })
    let sorted = input.sorted {
        if $0.lowerBound == $1.lowerBound {
            return $0.upperBound < $1.upperBound
        }
        return $0.lowerBound < $1.lowerBound
    }
    var result: [Slot] = []
    for slot in sorted {
        if let last = result.last,
           slot.lowerBound < last.upperBound {
            result[result.count - 1] =
                last.lowerBound..<max(last.upperBound, slot.upperBound)
        } else {
            result.append(slot)
        }
    }
    return result
}

func peak(_ input: [Slot]) -> Int {
    precondition(input.allSatisfy { !$0.isEmpty })
    let events = input.flatMap {
        [(time: $0.lowerBound, delta: 1),
         (time: $0.upperBound, delta: -1)]
    }.sorted {
        if $0.time == $1.time {
            return $0.delta < $1.delta
        }
        return $0.time < $1.time
    }
    var active = 0
    var maximum = 0
    for event in events {
        active += event.delta
        maximum = max(maximum, active)
    }
    return maximum
}

precondition(merged([]).isEmpty)
precondition(peak([]) == 0)
precondition(merged([0..<10, 10..<20]) == [0..<10, 10..<20])
precondition(peak([0..<10, 10..<20]) == 1)
precondition(merged([0..<10, 5..<15, 10..<20]) == [0..<20])
precondition(peak([0..<10, 5..<15, 10..<20]) == 2)
precondition(merged([0..<30, 5..<10, 8..<12]) == [0..<30])
precondition(peak([0..<30, 5..<10, 8..<12]) == 3)
precondition(peak([0..<10, 0..<10]) == 2)

Führen Sie im Terminal folgenden Befehl aus:

xcrun swift Intervals.swift

Bei erfolgreicher Prüfung gibt es keine Ausgabe, und der Exitcode ist null. Durch precondition statt ausschließlich assert bleiben die Tests auch dann wirksam, wenn Assertions in einem gewöhnlichen optimierten Build deaktiviert werden. Auch das Prüfskript darf keine Compileroptionen verwenden, die Sicherheitsprüfungen abschalten.

Ereignisse zum selben Zeitpunkt und verschachtelte Intervalle prüfen

Der Sweep-Line-Algorithmus zählt bei jedem Beginn eins hinzu und zieht bei jedem Ende eins ab. Zum selben Zeitpunkt müssen zuerst die Endereignisse und danach die Startereignisse verarbeitet werden. Andernfalls werden zwei direkt aufeinanderfolgende Buchungen kurzzeitig als gleichzeitig gezählt. Nur nach dem Zeitpunkt zu sortieren, ohne diese Reihenfolge ausdrücklich festzulegen, ist eine häufige Fehlerquelle an den Intervallgrenzen.

Bewahren Sie mindestens fünf Arten fester Testfälle auf: leere Liste, direkt aneinandergrenzende Intervalle, teilweise Überlappung, vollständige Einbettung und identische Duplikate. Ob zwei identische Intervalle zwei eigenständige Buchungen darstellen, ergibt sich aus den fachlichen Eingabedaten. Hier zählt jedes Element als eigene Belegung. Zwei vollständig identische Buchungen ergeben daher eine Gleichzeitigkeit von zwei.

Beim Zusammenführen wird ein weiteres Detail leicht übersehen: Beim Aktualisieren des rechten Endpunkts muss der größere Wert verwendet werden. Wird stattdessen einfach das Ende des aktuellen Intervalls übernommen, kann eine lange Buchung, die eine kurze enthält, durch das Zusammenführen sogar verkürzt werden. Auch unsortierte Eingaben müssen dasselbe Ergebnis liefern. Der Algorithmus darf sich nicht darauf verlassen, dass der Server die Daten zufällig bereits sortiert hat.

Mit einem unabhängigen Rechenweg gegenprüfen

Bei festen Testfällen kann sich derselbe Denkfehler sowohl in die Implementierung als auch in die erwarteten Ergebnisse einschleichen. Für kleine Stichproben mit ganzzahligen Zeitwerten lässt sich an jedem Zeitschritt zählen, wie viele Intervalle ihn enthalten. Das dient als unabhängige Referenz. Hängen Sie den folgenden Code an dieselbe Datei an, um ihn auszuführen. Er ist für Tests gedacht und ersetzt nicht den Produktionsalgorithmus.

func referencePeak(_ input: [Slot]) -> Int {
    guard let start = input.map(\.lowerBound).min(),
          let end = input.map(\.upperBound).max() else {
        return 0
    }
    return (start..<end).map { tick in
        input.filter { $0.contains(tick) }.count
    }.max() ?? 0
}

let candidates: [Slot] = (0..<5).flatMap { start in
    ((start + 1)...5).map { start..<$0 }
}

for first in candidates {
    for second in candidates {
        let sample = [first, second]
        precondition(peak(sample) == referencePeak(sample))
        precondition(merged(sample) ==
                     merged(Array(sample.reversed())))
        precondition(merged(merged(sample)) == merged(sample))
    }
}

Diese Prüfungen sichern jeweils die korrekte maximale Gleichzeitigkeit, die Unabhängigkeit von der Eingabereihenfolge und die Idempotenz des Zusammenführens ab. Der diskrete Referenzalgorithmus gilt nur für den hier festgelegten Vertrag mit ganzzahligen Zeitschritten. Daraus lässt sich nicht ableiten, dass beliebige kontinuierliche Zeitverläufe abgedeckt sind. Wenn Sie Zufallstests ergänzen, speichern Sie die fehlgeschlagenen Eingaben und nicht nur den Zufalls-Seed. So bleiben Fehler auch nach einem Wechsel der Toolchain reproduzierbar.

Vor der Integration Eingaben und Fehlernachweise absichern

Trennen Sie bei der Integration in das Projekt das Parsen, die Normalisierung und die Intervallberechnung in drei Schichten. Ermitteln Sie zunächst Start- und Endwerte auf derselben Zeitbasis, vereinheitlichen Sie anschließend die Genauigkeit und prüfen Sie zuletzt, ob das Ende strikt nach dem Beginn liegt. Durch die Umrechnung der Genauigkeit kann eine ursprünglich sehr kurze Buchung auf eine Dauer von null schrumpfen. Die Validierung darf deshalb nicht nur vor der Umrechnung erfolgen.

Wenn mehrere Räume dieselbe Buchungsliste nutzen, gruppieren Sie die Einträge zunächst nach Ressourcenkennung und berechnen Sie die Ergebnisse anschließend getrennt. Gleichzeitige Besprechungen in verschiedenen Räumen dürfen sich nicht gegenseitig als Konflikt auslösen. Sollen auch Personen nicht gleichzeitig mehrfach verplant werden, legen Sie für sie einen weiteren Satz von Ressourcenbedingungen an. Führen Sie nicht pauschal alle Buchungen in einem einzigen Sweep-Line-Durchlauf zusammen.

Für einen Fehlernachweis genügen die Ressourcenkennung, die normalisierten Intervalle, der erwartete und der tatsächliche Wert sowie die Version der Toolchain. Angaben zu den Teilnehmenden sind nicht erforderlich. Nehmen Sie die betreffende Eingabe vor der Korrektur in die festen Testfälle auf und führen Sie anschließend das vollständige Skript aus. Als abschließendes Erfolgskriterium müssen die Randfälle, die Referenzberechnung und die fachliche Gruppierung übereinstimmende Ergebnisse liefern. Es reicht nicht, dass eine bestimmte Oberfläche keine Konfliktmeldung mehr anzeigt.

Häufig gestellte Fragen