Line Sweep für maximale Überlappung
Zählen Sie gleichzeitig aktive Intervalle anhand von Ereignissen
Line Sweep für maximale Überlappung ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 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.
Die Frage nach der maximalen Überlappung
Wie viele Intervalle decken denselben Zeitpunkt gleichzeitig ab? Die maximale Anzahl ist die maximale Überlappung, also der am stärksten belegte Punkt auf Ihrer Zeitachse. 📈
Denken Sie in Ereignissen
Denken Sie nicht mehr in vollständigen Intervallen. Teilen Sie jedes Intervall in zwei Ereignisse auf: ein +1 beim Start und ein -1 beim Ende.
Erstellen Sie die Ereignisliste
Fügen Sie für jedes Intervall ein Start- und ein Endereignis zu einer gemeinsamen Liste hinzu. Jedes Ereignis enthält eine Position und ein Delta von plus oder minus eins.
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))Sortieren Sie die Ereignisse
Sortieren Sie jedes Ereignis nach seiner Position, damit Sie die Zeitachse von links nach rechts durchlaufen und Änderungen in der richtigen Reihenfolge verarbeiten können.
events.sort()Durchlaufen und zählen
Durchlaufen Sie die sortierten Ereignisse und führen Sie einen laufenden Zähler. Addieren Sie jedes Delta, sobald Sie es erreichen. Der Zähler gibt dann an, wie viele Intervalle gerade aktiv sind.
active = 0
for pos, delta in events:
active += deltaVerfolgen Sie den Höchstwert
Vergleichen Sie den Zähler nach jeder Aktualisierung mit Ihrem bisherigen Bestwert. Der größte Wert, den der Zähler jemals erreicht, ist die maximale Überlappung.
best = max(best, active)Der Trick bei Gleichständen
Bei gleichen Positionen ist die Reihenfolge entscheidend. Wenn ein Ende bei x den Platz vor einem Start bei x freigeben soll, sortieren Sie Enden am selben Punkt vor Starts.
Deltas für die richtige Sortierung codieren
Eine elegante Möglichkeit, Gleichstände aufzulösen, besteht darin, die Deltas so zu wählen, dass die Tupelsortierung dies automatisch erledigt. Platzieren Sie das -1-Delta vor dem +1-Delta, wenn die Positionen übereinstimmen.
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tieWarum es schnell ist
Sie erstellen 2n Ereignisse, sortieren sie einmal und führen einen Sweep durch. Das gesamte Verfahren läuft in O(n log n), wobei der einmalige Sortiervorgang den größten Anteil ausmacht.
Wo Sie es sehen
Mit der maximalen Überlappung lassen sich klassische Aufgaben lösen, etwa die Bestimmung der mindestens benötigten Räume für Besprechungen oder der maximalen Anzahl gleichzeitiger Benutzer auf einem Server.
Mehr als nur zählen
Dasselbe Sweep-Verfahren lässt sich leicht erweitern: Verfolgen Sie die insgesamt abgedeckte Länge oder finden Sie jede Position, an der sich die Anzahl ändert – alles in einem einzigen linearen Durchlauf.
Schnelltest
Sie durchlaufen Ereignisse, um die maximale Überlappung zu finden.
Zusammenfassung
Wandeln Sie Intervalle in +1-Start- und -1-Ende-Ereignisse um, sortieren Sie sie und durchlaufen Sie sie mit einem Zähler, um den Höchstwert zu finden. Lösen Sie Gleichstände auf, indem Sie Enden vor Starts verarbeiten. 🚀
Häufig gestellte Fragen
Ist die Lektion „Line Sweep für maximale Überlappung“ kostenlos?
Ja — der vollständige Text von „Line Sweep für maximale Ü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 „Line Sweep für maximale Überlappung“?
Zählen Sie gleichzeitig aktive Intervalle anhand von Ereignissen 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 3 von 4.
Wie lange dauert die Lektion „Line Sweep für maximale Ü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