Minimale Entfernung für keine Überlappung
Greedy-Planung durch Behalten der frühesten Enden
Minimale Entfernung für keine Überlappung ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 4 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 Entfernens
Sie haben sich überlappende Intervalle und möchten möglichst wenige entfernen, damit keine Überlappungen mehr bestehen. Behalten Sie so viele wie möglich. ✂️
Drehen Sie das Problem um
Möglichst wenige Intervalle zu entfernen ist dasselbe, wie möglichst viele nicht überlappende Intervalle zu behalten. Lösen Sie die Behalten-Variante; anschließend ergibt sich die Anzahl der Entfernungen als n minus die Anzahl der behaltenen Intervalle.
Das ist die Aktivitätsauswahl
Möglichst viele nicht überlappende Intervalle zu behalten, ist im Grunde das klassische Problem der Aktivitätsauswahl. Dieselbe Greedy-Idee löst beide Varianten.
Nach dem Ende sortieren
Hier ist die richtige Reihenfolge die Sortierung nach der Endzeit, nicht nach dem Start. Wer früh fertig ist, gibt die Zeitachse am schnellsten für das nächste möglicherweise zu behaltende Intervall frei.
intervals.sort(key=lambda x: x[1])Die Greedy-Wahl
Behalten Sie unter den noch kompatiblen Intervallen immer dasjenige, das am frühesten endet. So bleibt möglichst viel Platz für die übrigen Intervalle.
Das Ende des letzten behaltenen Intervalls verfolgen
Speichern Sie das Ende des letzten Intervalls, das Sie behalten haben. Das nächste Intervall ist nur dann kompatibel, wenn sein Start auf oder nach dieser Grenze liegt.
if start >= last_end:
last_end = endDie Entfernungen zählen
Wenn ein Intervall vor last_end beginnt, steht es in Konflikt. Verwerfen Sie es und erhöhen Sie den Zähler der Entfernungen um eins. Andernfalls behalten Sie es.
else:
removed += 1Warum das früheste Ende gewinnt
Das beweist ein Austauschargument: Wenn Sie ein beliebiges behaltenes Intervall durch das kompatible Intervall mit dem frühesten Ende ersetzen, verringert sich die Anzahl der behaltenen Intervalle nie.
Die Randbedingung bei Berührung beachten
Entscheiden Sie, ob [1, 2] und [2, 3] als überlappend gelten. Wenn das Teilen eines Endpunkts erlaubt ist, verwenden Sie start >= last_end als Test.
Das vollständige Greedy-Verfahren
Sortieren Sie nach dem Ende, durchlaufen Sie die Intervalle einmal und zählen Sie die Konflikte. Die Gesamtlaufzeit beträgt wegen des Sortierens plus eines einzigen linearen Durchlaufs O(n log n).
removed = 0; last_end = float('-inf')
for s, e in intervals:
if s >= last_end: last_end = e
else: removed += 1Eine vertraute Struktur
Mit diesem Muster planen Sie möglichst viele Besprechungen in einem Raum oder platzieren möglichst viele Aufgaben auf einer Maschine. Erkennen Sie es immer dann, wenn Konflikte minimiert werden müssen.
Schnelltest
Sie behalten nicht überlappende Intervalle nach einem Greedy-Verfahren.
Zusammenfassung
Die minimale Anzahl der Entfernungen ist n minus die größtmögliche Anzahl, die Sie behalten können. Sortieren Sie nach dem Ende, behalten Sie nach dem Greedy-Prinzip kompatible Intervalle mit dem frühesten Ende und zählen Sie den Rest. 🚀
Häufig gestellte Fragen
Ist die Lektion „Minimale Entfernung für keine Überlappung“ kostenlos?
Ja — der vollständige Text von „Minimale Entfernung für keine Überlappung“ 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 „Minimale Entfernung für keine Überlappung“?
Greedy-Planung durch Behalten der frühesten Enden 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 4 von 4.
Wie lange dauert die Lektion „Minimale Entfernung für keine Überlappung“?
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