Meeting Rooms II

Q: Wie hoch ist die Zeitkomplexität von Meeting Rooms II?

Beide schnellen Lösungen haben eine Laufzeit von O(n log n) . Die Heap-Version sortiert die Besprechungen und führt pro Besprechung eine Heap-Operation mit O(log n) aus; die Version mit zwei Listen sortiert zweimal und durchläuft die Listen einmal in O(n) . Beide benötigen zusätzlichen Speicherplatz von O(n) . Die Anzahl der laufenden Besprechungen bei jedem Start zu zählen, benötigt O(n²) .

MittelIntervalle Heap Sortieren

+10

Du erhältst eine Liste von Besprechungen als zwei Arrays: Besprechung i läuft von starts[i] bis ends[i]. In einem Raum findet jeweils nur eine Besprechung statt, und eine Besprechung kann in einem Raum genau dann beginnen, wenn dort eine andere Besprechung endet.

Schreibe eine Funktion namens minMeetingRooms, die die kleinste Anzahl an Räumen zurückgibt, in denen alle Besprechungen stattfinden können.

Funktion

minMeetingRooms(starts: integer-array, ends: integer-array) → integer

startsinteger-array: die Startzeit jeder Besprechung
endsinteger-array: die Endzeit jedes Meetings am selben Index wie dessen Startzeit
Gibt zurückinteger: die wenigsten Räume, in denen alle Besprechungen stattfinden können

Einschränkungen

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
Die Besprechungen sind nicht sortiert. Zwei Besprechungen können identisch sein.

Beispiele

Eingabe: starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
Ausgabe: 3
Erklärung: Zum Zeitpunkt 4 laufen die Besprechungen von 1 bis 5, von 2 bis 6 und von 4 bis 8 alle gleichzeitig, daher brauchst du mindestens 3 Räume. Drei reichen aus: Die Besprechung von 7 bis 9 nutzt den Raum, der um 5 frei wird.

Eingabe: starts = [0, 2, 3]ends = [10, 3, 5]
Ausgabe: 2
Erklärung: Das Meeting von 0 bis 10 belegt während der gesamten Zeit einen Raum. Das Meeting von 2 bis 3 benötigt einen zweiten Raum, und das Meeting von 3 bis 5 nutzt denselben Raum, sobald er frei wird, sodass 2 Räume ausreichen.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du auch angeben, welchem Raum jedes Meeting zugeordnet wird, ohne mehr Räume als in der Antwort zu verwenden?

Lösung

Die Anzahl der benötigten Räume entspricht der größten Anzahl gleichzeitig stattfindender Meetings. Die Anzahl der laufenden Meetings zu jedem Startzeitpunkt zu zählen, findet sie in O(n²). Durch Sortieren wird aus der Frage ein einziger Durchlauf durch den Tag: Ein Min-Heap mit den Zeitpunkten, zu denen Räume frei werden, oder zwei sortierte Listen mit Start- und Endzeitpunkten liefern die Antwort in O(n log n).

Anzahl der laufenden Meetings zu jedem Startzeitpunkt

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Zu jedem Zeitpunkt benötigt jede laufende Besprechung einen eigenen Raum. Du brauchst also mindestens so viele Räume wie die größte Anzahl gleichzeitig laufender Besprechungen. So viele reichen auch aus: Weise die Räume nach Startzeit zu, und ein neuer Raum wird nur dann eröffnet, wenn alle Räume belegt sind – das bedeutet, dass genau dann so viele Besprechungen gleichzeitig laufen.

Die Anzahl der laufenden Besprechungen steigt nur, wenn eine Besprechung beginnt. Der Zeitpunkt mit den meisten laufenden Besprechungen ist also der Beginn einer Besprechung. Zähle für jede Besprechung i die Besprechungen j mit starts[j] ≤ starts[i] < ends[j]: Sie haben bereits begonnen und sind noch nicht beendet. Eine Besprechung, die genau bei starts[i] endet, wird nicht mitgezählt, da ihr Raum in diesem Moment wieder frei ist.

Im ersten Beispiel laufen zum Zeitpunkt 4 die Besprechungen von 1 bis 5, von 2 bis 6 und von 4 bis 8: 3. Zum Zeitpunkt 7 laufen nur die Besprechungen von 4 bis 8 und von 7 bis 9: 2. Die größte Anzahl ist 3.

Jede der n Besprechungen durchsucht alle n Besprechungen. Bei n = 5000 sind das 25 Millionen Prüfungen: ein Bruchteil einer Sekunde in C, mehrere Sekunden in Python oder R und jedes Mal viermal so viele, wenn sich n verdoppelt.

Algorithmus

Setze für jedes Meeting i running auf 0.
Addiere für jedes Meeting j 1 zu running, wenn starts[j] ≤ starts[i] < ends[j].
Behalte den größten Wert von running, den du gesehen hast.
Gib diesen größten Wert zurück.

def minMeetingRooms(starts, ends):
    n = len(starts)
    most = 0
    for i in range(n):
        # how many meetings are running at the moment meeting i starts
        running = 0
        for j in range(n):
            if starts[j] <= starts[i] < ends[j]:
                running += 1
        most = max(most, running)
    return most

Min-Heap der Zeiten, zu denen Räume frei werden

Idee

Weise den Besprechungen Räume zu, wie es jemand an einer Rezeption tun würde. Nimm die Besprechungen in der Reihenfolge ihrer Startzeit. Sieh dir für jede an, welcher Raum als Erstes frei wird. Wenn er zum Startzeitpunkt der Besprechung frei ist, bekommt die Besprechung diesen Raum. Andernfalls sind alle Räume noch belegt, also öffnest du einen neuen.

Es ist sicher, nur diesen einen Raum zu prüfen. Wenn der Raum, der als Erstes frei wird, noch belegt ist, sind es alle. Wenn er frei ist, ist jeder freie Raum genauso gut wie ein anderer: Die noch kommenden Besprechungen beginnen zu diesem Zeitpunkt oder später, daher bleibt jeder Raum, der jetzt frei ist, für alle frei.

Du brauchst den frühesten Zeitpunkt, zu dem ein Raum frei wird, und dieser ändert sich nach jeder Besprechung. Ein Min-Heap speichert eine Endzeit pro Raum und gibt dir den kleinsten Wert. Wenn du einen Raum wiederverwendest, ersetzt du seine Endzeit durch das Ende der neuen Besprechung; wenn du einen Raum öffnest, fügst du eine neue Endzeit hinzu. Im ersten Beispiel ergeben sich nach dem Sortieren nach Startzeit: 1 bis 5 ergibt [5], 2 bis 6 ergibt [5, 6], 4 bis 8 ergibt [5, 6, 8], und bei 7 bis 9 wird 5 als kleiner oder gleich 7 gefunden und ersetzt, sodass [6, 8, 9] übrig bleibt. Drei Räume.

Das Sortieren kostet O(n log n), und für jede Besprechung ist eine Heap-Operation mit O(log n) nötig. Python-heapq, Javas PriorityQueue, C++-priority_queue mit greater, Rusts BinaryHeap mit Reverse, Gos container/heap und PHPs SplMinHeap stellen dir den Heap bereit. In den anderen Sprachen verwaltest du ihn in einem Array: Der Elternknoten von Index i befindet sich bei (i-1)/2, und ein Wert steigt nach oben, solange er kleiner als sein Elternknoten ist.

Algorithmus

Sortiere die Besprechungen nach Beginn und behalte dabei jeden Beginn mit seinem eigenen Ende zusammen.
Prüfe für jede Besprechung: Wenn der Heap nicht leer ist und sein kleinstes Ende vor oder zum Beginn der Besprechung liegt, ersetze dieses Ende durch das Ende der Besprechung.
Andernfalls füge das Ende der Besprechung hinzu: Ein neuer Raum wird geöffnet.
Gib die Größe des Heaps zurück, mit einem Eintrag pro Raum.

import heapq


def minMeetingRooms(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    free_at = []  # a min-heap: when each room's last meeting ends
    for start, end in meetings:
        if free_at and free_at[0] <= start:
            heapq.heapreplace(free_at, end)  # the earliest free room is free now: reuse it
        else:
            heapq.heappush(free_at, end)  # every room is busy: open a new one
    return len(free_at)

Starts und Enden separat sortieren

Idee

Der Heap speichert, welche Endzeit zu welchem Raum gehört, aber die Antwort ist nur eine Anzahl. Wenn ein Meeting beginnt, ist nur wichtig, ob bis dahin ein anderes Meeting beendet ist und einen Raum freigegeben hat; welches Meeting es war, spielt keine Rolle. Sortiere also die Starts und die Enden als zwei separate Listen und gehe die Starts mit einem Zeiger ended in den Enden durch.

Für jeden Start der Reihe nach: Wenn er bei oder nach endTimes[ended] liegt, ist bis dahin ein Meeting beendet. Sein Raum nimmt das neue Meeting auf, und ended rückt weiter. Andernfalls sind alle genutzten Räume noch belegt, und rooms erhöht sich um eins. Jeder Start verbraucht höchstens ein Ende, genauso wie ein wiederverwendeter Raum im Heap ein altes Ende durch ein neues ersetzt.

Im ersten Beispiel sind die Starts 1, 2, 4, 7 und die Enden 5, 6, 8, 9. Die Starts 1, 2 und 4 liegen alle vor Ende 5, daher steigt rooms auf 3. Start 7 liegt bei oder nach 5, also nutzt er diesen Raum wieder, und ended rückt zu Ende 6 weiter. Die Antwort ist 3. Das ≥ ist der Grund, warum Meetings, die direkt aneinander anschließen, einen Raum teilen können: Im zweiten Beispiel trifft Start 12 auf Ende 12 und nutzt den Raum wieder.

Die Anzahl überschreitet nie den tatsächlichen Höchstwert: Wenn rooms steigt, liegt das nächste Ende noch in der Zukunft, sodass in diesem Moment alle rooms Meetings laufen. Sie erreicht auch den Höchstwert, denn ein Start überspringt das Öffnen eines Raums nur dann, wenn ein tatsächliches Ende zu diesem oder einem früheren Zeitpunkt einen Raum freigegeben hat. Zwei Sortierungen kosten O(n log n), der Durchlauf O(n) und die sortierten Kopien O(n) Speicherplatz.

Algorithmus

Sortiere eine Kopie der Startzeiten und eine Kopie der Endzeiten.
Setze rooms und ended auf 0.
Für jeden Startzeitpunkt der Reihe nach gilt: Liegt er bei oder nach endTimes[ended], erhöhe ended um 1: Das Meeting belegt einen frei gewordenen Raum.
Andernfalls erhöhe rooms um 1.
Gib rooms zurück.

def minMeetingRooms(starts, ends):
    start_times = sorted(starts)
    end_times = sorted(ends)
    rooms = 0
    ended = 0  # how many meetings have ended, earliest end first
    for start in start_times:
        if start >= end_times[ended]:
            ended += 1  # a meeting has ended by now: this one takes its room
        else:
            rooms += 1  # every room is busy: open a new one
    return rooms

Stolperfallen und Grenzfälle

Die meisten Fehler entstehen beim Vergleich an einem Berührungspunkt oder bei der Frage, welcher Raum geprüft wird.

Prüfen von start > end statt start ≥ end. Dann kann eine Besprechung einen Raum nicht genau in dem Moment nutzen, in dem er frei wird, und die Besprechungen von 10 bis 12, 12 bis 14 und 14 bis 16 benötigen 2 Räume statt 1.
Prüfen des zuletzt geöffneten Raums statt des Raums, der als Erstes frei wird. Bei den Besprechungen von 1 bis 3, 2 bis 10 und 4 bis 6 ist der zuletzt geöffnete Raum bis 10 belegt. Deshalb öffnest du einen dritten Raum, obwohl der erste seit 3 frei ist.
Die größte Anzahl von Besprechungen, die sich mit einer Besprechung überschneiden, nehmen und 1 addieren. Die Besprechung von 0 bis 10 überschneidet sich mit den Besprechungen von 2 bis 3 und von 3 bis 5, aber diese beiden überschneiden sich nicht miteinander. Daher reichen 2 Räume aus, nicht 3.
Die beiden sortierten Ansätze verwechseln. Beim Heap muss jedes Ende vor dem Sortieren nach Startzeit seinem eigenen Start zugeordnet sein; beim Ansatz mit zwei Listen werden die Start- und Endzeiten absichtlich getrennt sortiert.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Meeting Rooms II?

Beide schnellen Lösungen haben eine Laufzeit von O(n log n). Die Heap-Version sortiert die Besprechungen und führt pro Besprechung eine Heap-Operation mit O(log n) aus; die Version mit zwei Listen sortiert zweimal und durchläuft die Listen einmal in O(n). Beide benötigen zusätzlichen Speicherplatz von O(n). Die Anzahl der laufenden Besprechungen bei jedem Start zu zählen, benötigt O(n²).

Warum löst ein Min-Heap das Problem „Meeting Rooms II“?

Wenn du die Meetings in der Reihenfolge ihrer Startzeiten durchgehst, lohnt es sich nur, den Raum zu prüfen, der zuerst frei wird. Ein Min-Heap der Endzeiten liefert dir diesen Raum in O(1) und lässt sich in O(log n) aktualisieren. Der Heap wächst nur, wenn alle Räume belegt sind, daher entspricht seine endgültige Größe der geringsten Anzahl an Räumen, die benötigt wird.

Kann Meeting Rooms II ohne einen Heap gelöst werden?

Ja. Sortiere die Startzeiten und die Endzeiten als zwei separate Listen und gehe die Startzeiten mit einem Zeiger in der Endzeitenliste durch. Ein Start zur selben Zeit wie oder nach dem nächsten noch nicht verwendeten Ende nutzt einen Raum erneut; jeder andere Start eröffnet einen Raum. Dieselbe Idee funktioniert als Sweep-Line: Wandle jedes Meeting in ein +1-Ereignis am Start und ein -1-Ereignis am Ende um, verarbeite Enden bei gleichen Zeiten vor Starts und verfolge die größte laufende Summe.

Ist die Antwort gleich der maximalen Anzahl von Meetings, die sich zu einem Zeitpunkt überschneiden?

Ja. Gleichzeitig stattfindende Besprechungen benötigen unterschiedliche Räume, also brauchst du mindestens so viele. Wenn du jeder Besprechung in der Reihenfolge ihres Beginns einen beliebigen freien Raum zuweist, brauchst du nie mehr Räume. Daher ist die maximale Anzahl gleichzeitig stattfindender Besprechungen genau die Antwort.

Python

def minMeetingRooms(starts, ends):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

starts = [4, 1, 7, 2]
ends = [8, 5, 9, 6]

Erwartet

Meeting Rooms II

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Anzahl der laufenden Meetings zu jedem Startzeitpunkt

Min-Heap der Zeiten, zu denen Räume frei werden

Starts und Enden separat sortieren

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben