Meeting Rooms

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

Das Sortieren der Besprechungen nach Startzeit kostet O(n log n) , und der Durchlauf, bei dem benachbarte Elemente verglichen werden, kostet O(n) , also beträgt der Gesamtaufwand O(n log n) . Der Vergleich jedes Paars kostet stattdessen O(n²) .

Q: Warum reicht es aus, jedes Meeting mit dem vorherigen zu vergleichen?

Nach dem Sortieren nach Startzeit bilden die Besprechungen, sofern bisher keine Überschneidung gefunden wurde, eine Kette, in der jede Besprechung zum Zeitpunkt oder nach dem Ende der vorherigen beginnt. Die letzte Besprechung in der Kette endet am spätesten. Eine neue Besprechung, die zum Zeitpunkt oder nach ihrem Ende beginnt, kann sich mit keiner der früheren Besprechungen überschneiden.

Q: Gelten Besprechungen, die sich berühren, als überlappend?

In diesem Problem gilt das nicht: Ein Meeting darf genau in dem Moment beginnen, in dem ein anderes endet. Deshalb ist die Prüfung ein strikter Vergleich: start < previous end . Wenn sich Meetings nicht berühren dürften, würde die Prüfung zu start ≤ previous end werden.

Q: Wie findest du die minimale Anzahl an Besprechungsräumen?

Sortiere die Startzeiten und die Endzeiten als zwei separate Listen und gehe dann beide durch: Jeder Start belegt einen Raum, und jedes Ende, das vor oder gleichzeitig mit dem nächsten Start liegt, gibt einen Raum frei. Die größte Anzahl gleichzeitig belegter Räume ist die Antwort. Die Ja-oder-Nein-Frage hier zu beantworten, ist dasselbe wie zu fragen, ob ein Raum ausreicht.

LeichtIntervalle Sortieren

+10

Du erhältst eine Liste von Besprechungen in Form von zwei Arrays: Besprechung i dauert von starts[i] bis ends[i]. Eine Person möchte an allen Besprechungen teilnehmen, daher dürfen sich keine zwei Besprechungen überschneiden. Eine Besprechung darf genau zu dem Zeitpunkt beginnen, an dem eine andere endet. Gib true zurück, wenn die Person an jeder Besprechung teilnehmen kann, andernfalls false.

Funktion

canAttendMeetings(starts: integer-array, ends: integer-array) → boolean

startsinteger-array: die Startzeit jedes Treffens
endsinteger-array: die Endzeit jedes Meetings am selben Index wie seine Startzeit
Gibt zurückboolean: true, wenn sich keine zwei Besprechungen überschneiden, andernfalls false

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 = [9, 13, 10]ends = [10, 15, 12]
Ausgabe: true
Erklärung: In zeitlicher Reihenfolge finden die Besprechungen von 9 bis 10, von 10 bis 12 und von 13 bis 15 Uhr statt. Die zweite beginnt genau in dem Moment, in dem die erste endet. Das ist zulässig, daher lautet die Antwort true.

Eingabe: starts = [1, 4, 7]ends = [5, 6, 8]
Ausgabe: false
Erklärung: Das Treffen von 1 bis 5 läuft um 4 noch, wenn das Treffen von 4 bis 6 beginnt, also lautet die Antwort false.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Wenn Besprechungen einzeln gebucht werden: Wie würdest du jede neue Buchung in O(log n) mit dem Zeitplan abgleichen, ohne alles erneut zu sortieren?

Lösung

Die Prüfung jedes Meetingpaars findet alle Überschneidungen, kostet aber O(n²). Durch das Sortieren nach Startzeit ändert sich die Fragestellung: Ein Meeting kann dann nur noch mit seinem Nachbarn in der sortierten Reihenfolge kollidieren, sodass ein Vergleich pro Meeting genügt.

Vergleiche jedes Paar

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

Idee

Zwei Besprechungen überschneiden sich, wenn jede beginnt, bevor die andere endet. Bei Besprechungen von 1 bis 5 und von 4 bis 6 gilt: 1 liegt vor 6 und 4 liegt vor 5, also überschneiden sie sich. Bei Besprechungen von 9 bis 10 und von 10 bis 12 gilt: 10 liegt nicht vor 10, also berühren sie sich nur.

Die strikte Verwendung von < auf beiden Seiten ermöglicht es, dass eine Besprechung genau dann beginnt, wenn eine andere endet. Führe den Test für jedes Paar aus und gib beim ersten Überschneiden false zurück.

Der Haken ist die Anzahl der Paare. Bei n = 5000 Besprechungen gibt es etwa 12,5 Millionen Paare, und bei einem Zeitplan ohne Überschneidungen musst du sie alle überprüfen, was für die größten Tests zu langsam ist.

Algorithmus

Für jeden Index i und jeden Index j danach:
Wenn starts[i] < ends[j] und starts[j] < ends[i], überschneiden sich die beiden Besprechungen: Gib false zurück.
Wenn sich kein Paar überschneidet, gib true zurück.

def canAttendMeetings(starts, ends):
    n = len(starts)
    for i in range(n):
        for j in range(i + 1, n):
            # two meetings clash when each one starts before the other ends
            if starts[i] < ends[j] and starts[j] < ends[i]:
                return False
    return True

Nach Start sortieren und Nachbarn überprüfen

Idee

Sortiere die Besprechungen nach ihrer Startzeit und behalte dabei jeden Start zusammen mit seinem Ende. Betrachte nun eine beliebige Besprechung und die direkt davor. Wenn die frühere nach dem Beginn der späteren endet, überschneiden sie sich. Andernfalls beginnt die spätere Besprechung zum Zeitpunkt, an dem die frühere endet, oder danach.

Warum musst du nur die benachbarte Besprechung überprüfen? Wenn jede bisherige Besprechung zum Zeitpunkt, an dem die vorherige endet, oder danach beginnt, überschneiden sich die bisherigen Besprechungen nie, und die direkt vorherige ist diejenige, die zuletzt endet. Eine neue Besprechung, die zum Zeitpunkt ihres Endes oder danach beginnt, beginnt auch zum Zeitpunkt des Endes aller anderen oder danach.

Im ersten Beispiel lauten die sortierten Besprechungen 9 bis 10, 10 bis 12, 13 bis 15. Start 10 liegt nicht vor Ende 10, und Start 13 liegt nicht vor Ende 12, also gibt es keine Überschneidung. Gleiche Startzeiten führen immer zu einer Überschneidung, da jede Besprechung mindestens eine Zeiteinheit dauert; die Prüfung erkennt auch diese Fälle.

Das Sortieren kostet O(n log n), und das Durchlaufen kostet O(n). Die gepaarte Kopie der Besprechungen benötigt O(n) Speicherplatz.

Algorithmus

Ordne jedem Start das entsprechende Ende zu.
Sortiere die Paare nach Startzeit.
Vergleiche bei jedem Termin nach dem ersten dessen Start mit dem Ende des vorherigen Termins.
Ist der Start kleiner, gib false zurück.
Gib nach der Schleife true zurück.

def canAttendMeetings(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    for i in range(1, len(meetings)):
        # a meeting must not start before the one right before it ends
        if meetings[i][0] < meetings[i - 1][1]:
            return False
    return True

Stolperfallen und Grenzfälle

Häufige Fehler betreffen die Frage, welche Endpunkte miteinander verglichen werden und wie sich berührende Termine verhalten.

starts sortieren und ends in der Eingabereihenfolge belassen. Jedes Ende muss seinem eigenen Start zugeordnet bleiben, sonst vergleichst du einen Start mit dem Ende eines anderen Termins.
≤ statt < verwenden. Termine von 9 bis 10 und von 10 bis 12 berühren sich, überschneiden sich aber nicht; die Antwort dafür ist true.
Nur prüfen, ob jeder Termin endet, bevor der nächste in der Eingabereihenfolge beginnt. Die Eingabe ist nicht sortiert, daher sagen benachbarte Termine in der Eingabe nichts aus.
Den Paarvergleich mit nur einer Bedingung formulieren, etwa starts[j] < ends[i]. Das funktioniert nur, wenn Termin j später beginnt. Bei Terminen von 5 bis 6 und von 0 bis 1 in dieser Reihenfolge meldet 0 < 6 fälschlicherweise eine Überschneidung.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Meeting Rooms?

Das Sortieren der Besprechungen nach Startzeit kostet O(n log n), und der Durchlauf, bei dem benachbarte Elemente verglichen werden, kostet O(n), also beträgt der Gesamtaufwand O(n log n). Der Vergleich jedes Paars kostet stattdessen O(n²).

Warum reicht es aus, jedes Meeting mit dem vorherigen zu vergleichen?

Nach dem Sortieren nach Startzeit bilden die Besprechungen, sofern bisher keine Überschneidung gefunden wurde, eine Kette, in der jede Besprechung zum Zeitpunkt oder nach dem Ende der vorherigen beginnt. Die letzte Besprechung in der Kette endet am spätesten. Eine neue Besprechung, die zum Zeitpunkt oder nach ihrem Ende beginnt, kann sich mit keiner der früheren Besprechungen überschneiden.

Gelten Besprechungen, die sich berühren, als überlappend?

In diesem Problem gilt das nicht: Ein Meeting darf genau in dem Moment beginnen, in dem ein anderes endet. Deshalb ist die Prüfung ein strikter Vergleich: start < previous end. Wenn sich Meetings nicht berühren dürften, würde die Prüfung zu start ≤ previous end werden.

Wie findest du die minimale Anzahl an Besprechungsräumen?

Sortiere die Startzeiten und die Endzeiten als zwei separate Listen und gehe dann beide durch: Jeder Start belegt einen Raum, und jedes Ende, das vor oder gleichzeitig mit dem nächsten Start liegt, gibt einen Raum frei. Die größte Anzahl gleichzeitig belegter Räume ist die Antwort. Die Ja-oder-Nein-Frage hier zu beantworten, ist dasselbe wie zu fragen, ob ein Raum ausreicht.

Python

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

Testfälle

Fall 1

Fall 2

Eingabe

starts = [9, 13, 10]
ends = [10, 15, 12]

Erwartet

true