Aktivitätsauswahl nach frühestem Ende
Planen Sie möglichst viele nicht überlappende Ereignisse
Aktivitätsauswahl nach frühestem Ende ist eine kostenlose Coding Interview Prep-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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das Planungsproblem
Gegeben sind Veranstaltungen mit Anfangs- und Endzeiten. Bei der Aktivitätsauswahl sollen Sie möglichst viele Veranstaltungen besuchen, ohne dass sich zwei überschneiden. 📅
Überschneidungen bedeuten Konflikte
Zwei Aktivitäten überschneiden sich, wenn eine beginnt, bevor die andere endet. Aus jedem sich überschneidenden Paar dürfen Sie nur eine Veranstaltung auswählen.
Die entscheidende Regel
Der entscheidende greedy-Trick besteht darin, immer die unter den verfügbaren Veranstaltungen auszuwählen, die am frühesten endet. Ein frühes Ende lässt den größten zeitlichen Spielraum für weitere Veranstaltungen.
Nach Endzeit sortieren
Beginnen Sie damit, alle Aktivitäten nach ihrer Endzeit zu sortieren. Danach ist die beste nächste Wahl einfach die nächste passende Aktivität in dieser Reihenfolge.
events.sort(key=lambda e: e[1])Das letzte Ende speichern
Speichern Sie die letzte ausgewählte Endzeit in einer Variablen. Jede neue Veranstaltung muss zu diesem Zeitpunkt oder später beginnen, damit sie kompatibel ist.
last_end = -1Durchlaufen und auswählen
Durchlaufen Sie die sortierte Liste einmal. Wenn eine Veranstaltung bei last_end oder später beginnt, wählen Sie sie aus und aktualisieren last_end mit ihrer Endzeit.
for s, f in events:
if s >= last_end:
count += 1
last_end = fLaufzeit O(n log n)
Die Kosten entstehen durch das Sortieren in O(n log n) und anschließend durch einen einzigen linearen Durchlauf. Das ist selbst für sehr große Wettbewerbseingaben schnell genug.
Warum das früheste Ende gewinnt
Wer zuerst fertig ist, gibt die Zeitachse am frühesten wieder frei und kann daher niemals einen besseren Plan blockieren. Wird diese Aktivität in einen beliebigen optimalen Zeitplan eingesetzt, bleibt er genauso gut.
Der früheste Beginn scheitert
Die Auswahl nach dem frühesten Beginn kann eine lange Veranstaltung auswählen, die den ganzen Tag beansprucht. Auch die Dauer allein kann irreführend sein. Verlassen Sie sich daher auf die Endzeit.
Grenzfälle bei Berührungen behandeln
Entscheiden Sie, ob eine Veranstaltung, die genau dann endet, wenn eine andere beginnt, als Überschneidung gilt. Verwenden Sie s >= last_end, um direkt aufeinanderfolgende Veranstaltungen zu erlauben.
Ein häufiges Wettbewerbsmuster
Dieses Muster verbirgt sich hinter vielen Aufgaben: Räume buchen, Sendungen ansehen oder Aufträge ausführen. Erkennen Sie es, gilt die Regel des frühesten Endes.
Kurzer Check
Sie möchten die maximale Anzahl nicht überlappender Aktivitäten bestimmen.
Zusammenfassung
Sortieren Sie Aktivitäten nach ihrer Endzeit und wählen Sie anschließend jede Aktivität aus, die beginnt, nachdem Ihre letzte Auswahl endet. Eine Sortierung und ein Durchlauf liefern die größtmögliche Menge. 🚀
Häufig gestellte Fragen
Ist die Lektion „Aktivitätsauswahl nach frühestem Ende“ kostenlos?
Ja — der vollständige Text von „Aktivitätsauswahl nach frühestem Ende“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Aktivitätsauswahl nach frühestem Ende“?
Planen Sie möglichst viele nicht überlappende Ereignisse Du übst Coding Interview Prep 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep 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 „Aktivitätsauswahl nach frühestem Ende“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-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
- Die Greedy-Denkweise
- Aktivitätsauswahl nach frühestem Ende
- Fractional Knapsack nach Verhältnis
- Erkennen, wann Greedy scheitert