Intervalle nach Start sortieren
Ordnen Sie Ereignisse vor der Verarbeitung
Intervalle nach Start sortieren ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 1 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.
Was ein Intervall ist
Ein Intervall ist einfach ein Zahlenpaar aus Start und Ende, zum Beispiel [2, 5]. Die meisten Intervallprobleme bestehen aus einer Liste solcher Paare. 📏
Ordnung schafft Übersicht
Unsortierte Intervalle können in beliebiger Reihenfolge eintreffen, was die Analyse erschwert. Sortieren Sie sie zuerst, wird aus dem Chaos ein übersichtlicher Durchlauf von links nach rechts.
Nach dem Start sortieren
Normalerweise sortieren Sie nach dem Startwert. Nun beginnt jedes Intervall an oder nach der Position des vorherigen, sodass Sie die Liste einmal vorwärts durchlaufen können.
intervals.sort(key=lambda x: x[0])Tupel werden automatisch sortiert
Wenn Sie Intervalle als Tupel speichern, sortiert Python sie automatisch nach dem ersten Element und danach nach dem zweiten. Eine key-Funktion ist hier nicht erforderlich.
intervals = [(3, 7), (1, 4), (2, 5)]
intervals.sort()Warum zuerst nach dem Start sortieren
Durch die Sortierung nach dem Start verarbeiten Sie Ereignisse in zeitlicher Reihenfolge. Das nächste Intervall kann erst später beginnen – genau das ist die entscheidende Invariante für den Durchlauf.
Gleiche Startwerte
Wenn zwei Intervalle denselben Start haben, entscheidet der sekundäre Schlüssel über ihre Reihenfolge. Die Sortierung nach (start, end) platziert kürzere Intervalle zuerst, was oft hilfreich ist.
intervals.sort(key=lambda x: (x[0], x[1]))Manchmal nach dem Ende sortieren
Bei einigen Aufgaben, etwa bei der Planung möglichst vieler Ereignisse, wird stattdessen nach dem Ende sortiert. Wählen Sie den Schlüssel passend zu den Informationen, die Ihr Durchlauf benötigt.
intervals.sort(key=lambda x: x[1])Die Kosten des Sortierens
Das Sortieren benötigt O(n log n) Zeit. Das ist günstig und bestimmt bei diesen Problemen meist die Gesamtlaufzeit. Der anschließende Durchlauf benötigt nur O(n).
Zusätzliche Daten beibehalten
Wenn jedes Intervall eine ID oder ein Gewicht enthält, sortieren Sie den gesamten Datensatz, nicht nur die Grenzen. Der Schlüssel bestimmt die Reihenfolge, während die Daten mitgeführt werden.
intervals.sort(key=lambda iv: iv[0]) # iv = (start, end, id)Erst sortieren, dann durchlaufen
Fast jeder Intervallalgorithmus folgt dem Muster erst sortieren, dann durchlaufen. Wenn die Reihenfolge stimmt, werden Zusammenführen, Zählen und Planen zu einfachen Schleifen.
Ein einfaches mentales Modell
Stellen Sie sich die Intervalle als Gäste vor, die auf einer Party eintreffen. Durch die Sortierung nach dem Start stehen sie nach ihrer Ankunftszeit geordnet, sodass Sie sie einzeln begrüßen können.
Kurzer Check
Sie sind dabei, eine Liste von Intervallen zusammenzuführen.
Zusammenfassung
Ein Intervall ist ein Paar aus Start und Ende. Die Sortierung nach dem Start macht aus einer ungeordneten Liste einen übersichtlichen Durchlauf. Sortieren Sie zuerst und verarbeiten Sie die Intervalle anschließend in O(n) vorwärts. 🚀
Häufig gestellte Fragen
Ist die Lektion „Intervalle nach Start sortieren“ kostenlos?
Ja — der vollständige Text von „Intervalle nach Start sortieren“ 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 „Intervalle nach Start sortieren“?
Ordnen Sie Ereignisse vor der Verarbeitung 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 1 von 4.
Wie lange dauert die Lektion „Intervalle nach Start sortieren“?
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