Überlappende Intervalle zusammenführen
Kombinieren Sie Bereiche, die sich berühren oder überschneiden
Überlappende Intervalle zusammenführen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Das Ziel des Zusammenführens
Bei vielen Intervallen sollen sich berührende oder überlappende Intervalle zu möglichst wenigen nicht überlappenden Bereichen zusammenführen lassen. 🧩
Wann sich zwei Intervalle überlappen
Zwei Intervalle überlappen sich, wenn eines beginnt, bevor das andere endet. Nach der Sortierung nach dem Start bedeutet das, dass der nächste Start kleiner oder gleich dem aktuellen Ende ist.
Immer zuerst sortieren
Das Zusammenführen von links nach rechts funktioniert nur, wenn die Intervalle geordnet sind. Beginnen Sie daher mit dem Sortieren nach dem Start. Das ist die Grundlage des gesamten Durchlaufs.
intervals.sort(key=lambda x: x[0])Einen aktuellen Bereich behalten
Durchlaufen Sie die sortierte Liste und behalten Sie dabei ein aktuelles zusammengeführtes Intervall. Jedes neue Intervall erweitert es entweder oder beginnt einen neuen Bereich.
Bei Überlappung erweitern
Liegt der nächste Start innerhalb des aktuellen Bereichs, überlappen sich die Intervalle. Vergrößern Sie daher das aktuelle Ende auf das größere der beiden Enden.
cur_end = max(cur_end, end)Das maximale Ende verwenden
Verwenden Sie für das neue Ende immer max. Ein kurzes Intervall innerhalb eines langen darf den bereits aufgebauten Bereich nicht verkleinern.
Schließen und einen neuen Bereich öffnen
Liegt der nächste Start hinter dem aktuellen Ende, gibt es eine Lücke. Fügen Sie den abgeschlossenen Bereich Ihrem Ergebnis hinzu und beginnen Sie ein neues aktuelles Intervall.
result.append([cur_start, cur_end])Das letzte Intervall nicht vergessen
Die Schleife erstellt den letzten Bereich, fügt ihn aber nicht zum Ergebnis hinzu. Hängen Sie nach Ende der Schleife dieses letzte aktuelle Intervall mit append an, damit es nicht verloren geht.
Berühren zählt als Überlappung
Entscheiden Sie, ob [1, 3] und [3, 5] zusammengeführt werden sollen. Normalerweise ist das der Fall, verwenden Sie also start <= cur_end. Lesen Sie die Aufgabenstellung, um diese Randbedingung zu bestätigen.
Der vollständige Sweep
Ein Durchlauf nach dem Sortieren liefert alle zusammengeführten Bereiche. Daher läuft das gesamte Verfahren dank des Sortierens und eines linearen Sweeps in O(n log n).
for s, e in intervals[1:]:
if s <= cur_end:
cur_end = max(cur_end, e)
else:
result.append([cur_start, cur_end]); cur_start, cur_end = s, eEine häufige Anwendung
Das Zusammenführen ist für Kalender und Buchungssysteme nützlich: Fassen Sie belegte Zeitblöcke zusammen, um die tatsächlich freie Zeit zu sehen. Viele Wettbewerbsaufgaben haben genau diese Struktur.
Schnelltest
Sie führen Intervalle zusammen, nachdem Sie sie nach dem Start sortiert haben.
Zusammenfassung
Sortieren Sie nach dem Start, behalten Sie einen aktuellen Bereich und erweitern Sie ihn bei einer Überlappung mit max. Bei einer Lücke fügen Sie ihn ein und beginnen einen neuen Bereich. Denken Sie an das abschließende Einfügen. 🚀
Häufig gestellte Fragen
Ist die Lektion „Überlappende Intervalle zusammenführen“ kostenlos?
Ja — der vollständige Text von „Überlappende Intervalle zusammenführen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Überlappende Intervalle zusammenführen“?
Kombinieren Sie Bereiche, die sich berühren oder überschneiden Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Überlappende Intervalle zusammenführen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Intervalle nach Start sortieren
- Überlappende Intervalle zusammenführen
- Line Sweep für maximale Überlappung
- Minimale Entfernung für keine Überlappung