Intervallplanung und Zusammenführen
Lösen Sie die Probleme meeting-rooms und non-overlapping-intervals, indem Sie nach der Endzeit sortieren, und merge-intervals, indem Sie nach der Startzeit sortieren.
Intervallplanung und Zusammenführen 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.
Überblick über Intervallprobleme
Intervallprobleme kommen in Interviews zu Planung, Kalenderverwaltung und Ressourcenverteilung ständig vor. Die wichtigsten Muster sind: überlappende Intervalle zusammenführen, die minimale Anzahl an Besprechungsräumen bestimmen, die maximale Menge überlappungsfreier Intervalle finden und ein neues Intervall einfügen. Die meisten Intervallprobleme beginnen mit demselben Schritt: Intervalle nach dem Startzeitpunkt sortieren (oder je nach Problem nach dem Endzeitpunkt). Den richtigen Sortierschlüssel zu bestimmen, ist oft die schwierigste Aufgabe.
# Intervals: each = [start, end] (inclusive or exclusive by problem)
# Example:
intervals = [[1,3],[2,6],[8,10],[15,18]]
# Sorted by start (already sorted here)
# Visually:
# [1,3] |-|
# [2,6] |---|
# [8,10] |--|
# [15,18] |---|
print('Intervals ready for analysis')Überlappende Intervalle zusammenführen
Merge Intervals (LeetCode 56): Gegeben ist eine Liste von Intervallen; führen Sie alle überlappenden Intervalle zusammen. Algorithmus: Sortieren Sie nach dem Startzeitpunkt. Durchlaufen Sie die sortierte Liste. Wenn sich das aktuelle Intervall mit dem zuletzt zusammengeführten Intervall überschneidet (sein Start ≤ dem letzten zusammengeführten Ende), erweitern Sie das Ende des zuletzt zusammengeführten Intervalls auf das Maximum der beiden Endzeitpunkte. Andernfalls fügen Sie das aktuelle Intervall als neues zusammengeführtes Intervall hinzu. Zeit: O(n log n) für das Sortieren, O(n) für das Zusammenführen.
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0]) # sort by start
merged = [intervals[0]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end:
# Overlapping: extend the last interval
merged[-1][1] = max(last_end, end)
else:
# Non-overlapping: add as new interval
merged.append([start, end])
return merged
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]
print(merge_intervals([[1,4],[4,5]]))
# [[1,5]] (touching intervals merge)Intervall einfügen
Insert Interval (LeetCode 57): Gegeben ist eine sortierte, nicht überlappende Liste. Fügen Sie ein neues Intervall ein und führen Sie anschließend erneut zusammen. Durchlaufen Sie die Liste in drei Phasen: (1) Fügen Sie alle Intervalle hinzu, die enden, bevor das neue Intervall beginnt. (2) Führen Sie alle Intervalle zusammen, die sich mit dem neuen Intervall überschneiden (erweitern Sie dessen Grenzen). (3) Fügen Sie alle verbleibenden Intervalle hinzu. Nach dem Sortieren, das in diesem Problem bereits erfolgt ist, benötigen Sie dafür einen einzigen Durchlauf mit O(n).
def insert_interval(intervals, new_interval):
result = []
i = 0
n = len(intervals)
# Phase 1: intervals before new_interval
while i < n and intervals[i][1] < new_interval[0]:
result.append(intervals[i])
i += 1
# Phase 2: merge overlapping intervals
while i < n and intervals[i][0] <= new_interval[1]:
new_interval[0] = min(new_interval[0], intervals[i][0])
new_interval[1] = max(new_interval[1], intervals[i][1])
i += 1
result.append(new_interval)
# Phase 3: remaining intervals
while i < n:
result.append(intervals[i])
i += 1
return result
print(insert_interval([[1,3],[6,9]], [2,5])) # [[1,5],[6,9]]
print(insert_interval([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))
# [[1,2],[3,10],[12,16]]Meeting Rooms I: Können Sie alle Besprechungen besuchen?
Meeting Rooms I (LeetCode 252): Gegeben sind Zeitintervalle von Besprechungen. Bestimmen Sie, ob eine Person an allen Besprechungen teilnehmen kann. Sortieren Sie nach dem Startzeitpunkt. Wenn eine Besprechung beginnt, bevor die vorherige endet, überschneiden sie sich. Dies ist die einfachste Intervallprüfung – insgesamt O(n log n). Die entscheidende Erkenntnis: Nach dem Sortieren müssen Sie nur aufeinanderfolgende Paare vergleichen.
def can_attend_meetings(intervals):
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
# Current meeting starts before previous ends?
if intervals[i][0] < intervals[i-1][1]:
return False
return True
print(can_attend_meetings([[0,30],[5,10],[15,20]])) # False (0,30 overlaps 5,10)
print(can_attend_meetings([[7,10],[2,4]])) # True (4 < 7, no overlap)Meeting Rooms II: Minimale Anzahl an Räumen
Meeting Rooms II (LeetCode 253): Bestimmen Sie die minimale Anzahl an Konferenzräumen, die erforderlich ist, um alle Besprechungen gleichzeitig abzuhalten. Verwenden Sie einen Min-Heap, um den Raum zu verfolgen, der am frühesten frei wird. Sortieren Sie die Besprechungen nach dem Startzeitpunkt. Für jede neue Besprechung gilt: Beginnt sie nach dem Endzeitpunkt des am frühesten frei werdenden Raums, verwenden Sie diesen Raum erneut (entfernen Sie ihn und fügen Sie ihn wieder ein). Andernfalls öffnen Sie einen neuen Raum. Die Heap-Größe am Ende entspricht der benötigten Raumanzahl.
import heapq
def min_meeting_rooms(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[0]) # sort by start
heap = [] # min-heap of end times
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end) # reuse earliest-ending room
else:
heapq.heappush(heap, end) # open a new room
return len(heap)
print(min_meeting_rooms([[0,30],[5,10],[15,20]])) # 2
print(min_meeting_rooms([[7,10],[2,4]])) # 1
print(min_meeting_rooms([[9,10],[4,9],[4,17]])) # 2Sweep-Line-Alternative zur Raumanzahl
Eine alternative Lösung mit O(n log n) verwendet eine Sweep Line. Erstellen Sie für jeden Intervallbeginn ein Ereignis (+1) und für jedes Intervallende ein Ereignis (-1). Sortieren Sie alle Ereignisse nach der Zeit (bei gleichen Zeitpunkten: das Ende vor dem Beginn, wenn die Grenzen nicht inklusiv sein sollen). Durchlaufen Sie die Ereignisse von links nach rechts und führen Sie eine laufende Anzahl aktiver Besprechungen. Die maximale Anzahl entspricht der benötigten Mindestanzahl an Räumen. Dieser Ansatz ist für manche intuitiver und lässt sich auf andere Zählprobleme mit Intervallen verallgemeinern.
def min_rooms_sweep(intervals):
events = []
for start, end in intervals:
events.append((start, 1)) # meeting starts
events.append((end, -1)) # meeting ends
# Sort: same time → end (-1) before start (1) if exclusive
events.sort(key=lambda x: (x[0], x[1]))
max_rooms = current = 0
for _, delta in events:
current += delta
max_rooms = max(max_rooms, current)
return max_rooms
print(min_rooms_sweep([[0,30],[5,10],[15,20]])) # 2
print(min_rooms_sweep([[1,5],[2,6],[3,7]])) # 3 (all overlap at t=3)Überlappungsfreie Intervalle: Maximale Auswahl
Non-Overlapping Intervals (LeetCode 435): Bestimmen Sie die minimale Anzahl an Intervallen, die entfernt werden müssen, damit die übrigen Intervalle überlappungsfrei sind. Dies entspricht der Bestimmung der maximalen Anzahl überlappungsfreier Intervalle (Aktivitätsauswahl); die übrigen Intervalle werden anschließend als zu entfernende Intervalle zurückgegeben. Sortieren Sie nach dem Endzeitpunkt: Behalten Sie Greedy das Intervall, das am frühesten endet (dadurch bleibt maximaler Platz für künftige Intervalle). Wenn sich das nächste Intervall überschneidet, verwerfen Sie es und zählen eine Entfernung.
def erase_overlap_intervals(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[1]) # sort by END time
removals = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
last_end = end # keep this interval
else:
removals += 1 # remove this interval (it overlaps)
return removals
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]])) # 1 (remove [1,3])
print(erase_overlap_intervals([[1,2],[1,2],[1,2]])) # 2
print(erase_overlap_intervals([[1,2],[2,3]])) # 0 (no overlap)Warum nach der Endzeit und nicht nach der Startzeit sortieren?
Für die Aktivitätsauswahl (maximale Menge nicht überlappender Aktivitäten) ist das Sortieren nach der Endzeit nachweislich optimal. Die Intuition dahinter: Eine Aktivität, die früh endet, lässt mehr Platz für zukünftige Aktivitäten. Wenn wir nach der Startzeit sortieren, wählen wir möglicherweise eine sehr lange, früh beginnende Aktivität, die viele kürzere, später beginnende Aktivitäten blockiert. Austauschargument: Wenn die optimale Lösung die Aktivität A anstelle der am frühesten endenden Aktivität G auswählt, können wir A durch G ersetzen — G endet nicht später und überschneidet sich daher mit keiner Aktivität, mit der sich A nicht ebenfalls überschnitten hätte.
# Counterexample for sorting by START time:
# [[1,10],[2,3],[4,5]] — sorted by start: [1,10],[2,3],[4,5]
# Sort-by-start greedy keeps [1,10], can't add [2,3] or [4,5] (all overlap [1,10])
# Selects: 1 interval
# Sort-by-end greedy:
# [[2,3],[4,5],[1,10]] — sorted by end
# Keep [2,3] (end=3), then [4,5] (start=4 >= 3, keep), then [1,10] (start=1 < 5, skip)
# Selects: 2 intervals — OPTIMAL
intervals = [[1,10],[2,3],[4,5]]
intervals.sort(key=lambda x: x[1])
last_end = float('-inf')
count = 0
for s, e in intervals:
if s >= last_end:
count += 1; last_end = e
print('Max non-overlapping:', count) # 2Überschneidungen von Intervalllisten
Interval List Intersections (LeetCode 986): Finden Sie alle sich überschneidenden Paare aus zwei sortierten Intervalllisten. Verwenden Sie einen Ansatz mit zwei Zeigern. Berechnen Sie in jedem Schritt die Überschneidung des aktuellen Intervallpaars (Maximum der Startpunkte, Minimum der Endpunkte). Wenn der Startpunkt ≤ dem Endpunkt ist, ist die Überschneidung gültig. Bewegen Sie anschließend den Zeiger des Intervalls weiter, das zuerst endet. Laufzeit: O(m+n).
def interval_intersection(A, B):
result = []
i = j = 0
while i < len(A) and j < len(B):
# Intersection boundaries
lo = max(A[i][0], B[j][0])
hi = min(A[i][1], B[j][1])
if lo <= hi:
result.append([lo, hi]) # valid intersection
# Advance pointer of interval that ends first
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
print(interval_intersection(A, B))
# [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]Partitionierung von Labels
Partition Labels (LeetCode 763): Teilen Sie eine Zeichenkette in möglichst viele Teile auf, sodass jedes Zeichen in höchstens einem Teil vorkommt. Greedy-Ansatz: Ermitteln Sie für jedes Zeichen sein letztes Vorkommen. Durchlaufen Sie die Zeichenkette und verwalten Sie dabei ein max_end. Wenn i == max_end gilt, ist die aktuelle Partition abgeschlossen — speichern Sie ihre Länge und beginnen Sie eine neue Partition. Dies ist im Grunde ein Problem zum Zusammenführen von Intervallen.
def partition_labels(s):
last = {c: i for i, c in enumerate(s)} # last occurrence of each char
partitions = []
start = max_end = 0
for i, c in enumerate(s):
max_end = max(max_end, last[c])
if i == max_end: # partition complete
partitions.append(max_end - start + 1)
start = i + 1
return partitions
print(partition_labels('ababcbacadefegdehijhklij'))
# [9, 7, 8] — parts 'ababcbaca', 'defegde', 'hijhklij'Zusammenfassung der Intervallprobleme
Beherrschen Sie diese vier Muster für Intervalle: (1) Zusammenführen: Nach dem Startpunkt sortieren und bei einer Überschneidung das letzte Intervall erweitern. (2) Räume zählen: Nach dem Startpunkt sortieren und einen Min-Heap der Endzeiten verwenden. (3) Maximale Anzahl nicht überlappender Intervalle: Nach der Endzeit sortieren und gierig auswählen. (4) Einfügen: Linearer Scan in drei Phasen. Der Sortierschlüssel ist entscheidend: Beim Zusammenführen wird der Startpunkt verwendet, bei der maximalen Auswahl die Endzeit. Die Zeitkomplexität beträgt immer O(n log n), dominiert durch das Sortieren; das Zusammenführen bzw. Durchlaufen benötigt O(n).
# Quick reference:
# Merge intervals: sort by start, extend if overlap
# Insert interval: three-phase linear scan
# Meeting rooms (can?): sort by start, check consecutive overlap
# Meeting rooms (min?): sort by start, min-heap of end times / sweep
# Max non-overlapping: sort by END, greedy keep
# Min removals: n - max_non_overlapping
# Interval intersection: two pointers on sorted lists
print('Pattern: sort key is the decisive choice')
print('Merge → sort by start')
print('Activity selection → sort by end')
print('Room count → sort by start + heap of ends')Kurztest
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Intervalle werden zusammengeführt, indem sie nach dem Startpunkt sortiert und bei einer Überschneidung das letzte Intervall erweitert werden, für die minimale Anzahl an Besprechungsräumen werden die Intervalle nach dem Startpunkt sortiert und ein Min-Heap der Endzeiten verwendet, wobei Räume wiederverwendet werden, sobald der am frühesten endende Raum frei ist, und für die maximale Anzahl nicht überlappender Intervalle wird eine Greedy-Auswahl nach der Endzeit verwendet. Als Nächstes behandeln wir Jump Game I und II — Probleme zur Erreichbarkeit und zur minimalen Anzahl von Sprüngen, die durch eine gierige Erweiterung des erreichbaren Bereichs gelöst werden.
Häufig gestellte Fragen
Ist die Lektion „Intervallplanung und Zusammenführen“ kostenlos?
Ja — der vollständige Text von „Intervallplanung und 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 Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Intervallplanung und Zusammenführen“?
Lösen Sie die Probleme meeting-rooms und non-overlapping-intervals, indem Sie nach der Endzeit sortieren, und merge-intervals, indem Sie nach der Startzeit sortieren. 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 „Intervallplanung und 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 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
- Greedy vs. dynamische Programmierung: Wann wird was verwendet?
- Intervallplanung und Zusammenführen
- Jump Game I und II
- Task Scheduler und Gas Station