Minimum Platforms

Q: Wie hoch ist die zeitliche Komplexität des Problems mit der minimalen Anzahl an Bahnsteigen?

Das Sortieren der beiden Arrays kostet O(n log n) und der anschließende Durchlauf O(n) , daher bestimmen die Sortiervorgänge den Aufwand. Die sortierten Kopien benötigen zusätzlichen Speicherplatz von O(n) .

Q: Worin unterscheidet sich „Minimum Platforms“ von „Meeting Rooms II“?

Bei beiden geht es um die größtmögliche Anzahl an Intervallen, die sich zu einem Zeitpunkt überschneiden. Hier belegt ein Zug seinen Bahnsteig noch bis zu der Minute, in der er abfährt; bei „Meeting Rooms II“ ist ein Raum genau dann frei, wenn sein Meeting endet. Beim Sweep entspricht das einem Vergleich: Bei Gleichstand verarbeitest du hier zuerst die Ankunft und dort zuerst das endende Meeting.

Q: Kann das Problem der minimalen Bahnsteige ohne Sortieren gelöst werden?

Ja, da jede Zeit auf eine feste Uhrzeit abgebildet werden kann. Zähle die 2401 Indizes anhand der Zahl HHMM , addiere bei jeder Ankunft 1 und ziehe bei departure + 1 1 ab. Die größte laufende Summe ist die Antwort: Laufzeit O(n + 2400) . Indizes wie 1260 bis 1299 sind keine Uhrzeiten und erhalten keine Ankunft, daher bilden sie nie einen Höchstwert.

MittelSortieren Greedy Zwei Zeiger

+10

Ein Bahnhof hat einen Fahrplan für einen Tag: Zug i kommt um arrival[i] an und fährt um departure[i] ab. Die Zeiten sind Zahlen im Format HHMM, also Uhrzeiten ohne Doppelpunkt. 930 bedeutet daher 09:30 Uhr.

Ein Zug belegt seinen Bahnsteig ab der Minute seiner Ankunft bis einschließlich der Minute seiner Abfahrt. Ein Zug, der in derselben Minute ankommt, in der ein anderer abfährt, kann also nicht dessen Bahnsteig nutzen.

Gib die geringste Anzahl an Bahnsteigen zurück, die der Bahnhof benötigt, damit kein Zug warten muss.

Funktion

minimumPlatforms(arrival: integer-array, departure: integer-array) → integer

arrivalinteger-array: die Ankunftszeit jedes Zuges als HHMM-Zahl
departureinteger-array: die Abfahrtszeit jedes Zuges als HHMM-Zahl; departure[i] gehört zu arrival[i]
Gibt zurückinteger: die größte Anzahl von Zügen, die sich in derselben Minute am Bahnhof befinden, also die Mindestanzahl benötigter Bahnsteige

Einschränkungen

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
Jede Uhrzeit ist eine gültige HHMM-Uhrzeit: Ihre letzten beiden Ziffern sind höchstens 59.
Alle Züge fahren am selben Tag. Die Arrays sind nicht sortiert.

Beispiele

Eingabe: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
Ausgabe: 3
Erklärung: Um 15:30 stehen drei Züge am Bahnhof: die von 15:00 bis 16:00, von 15:20 bis 15:35 und von 15:30 bis 15:45. In keiner Minute sind es vier, daher reichen 3 Bahnsteige aus.

Eingabe: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
Ausgabe: 2
Erklärung: Der um 12:30 ankommende Zug trifft auf den um 12:30 abfahrenden Zug, und dasselbe passiert um 13:00. Zu jeder dieser Uhrzeiten befinden sich zwei Züge am Bahnhof, daher lautet die Antwort 2 und nicht 1.

Eingabe: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
Ausgabe: 2
Erklärung: Der Zug von 06:00 bis 22:00 belegt den ganzen Tag einen Bahnsteig. Die Züge von 07:00 bis 07:15 und von 13:00 bis 14:00 treffen sich nie, daher teilen sie sich einen zweiten Bahnsteig: 2.

Weiterführende Frage

Einige Nachtzüge kommen vor Mitternacht an und fahren danach ab, sodass ihre Abfahrtsnummer kleiner ist als ihre Ankunftsnummer. Wie würdest du die Bahnsteige zählen, wenn der Fahrplan um Mitternacht herumgeht?

Lösung

Die Antwort ist die größte Anzahl an Zügen am Bahnhof in derselben Minute. Die Aufgabe besteht darin, diese geschäftigste Minute zu finden, ohne jedes Zugpaar zu vergleichen. Sortiere Ankünfte und Abfahrten getrennt. Ein Durchlauf durch die Ereignisse des Tages mit einer laufenden Zählung findet sie in O(n log n).

Zähle die Züge bei jeder Ankunft

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

Idee

Züge, die in derselben Minute stehen, benötigen unterschiedliche Bahnsteige, daher ist die verkehrsreichste Minute eine Untergrenze. Sie reicht auch aus: Öffne einen neuen Bahnsteig nur dann, wenn ein ankommender Zug alle geöffneten Bahnsteige belegt vorfindet. In dieser Minute steht auf jedem geöffneten Bahnsteig ein Zug, außerdem auf dem neuen, sodass du nie mehr Bahnsteige öffnest als dem Spitzenwert entspricht.

Die Anzahl der anwesenden Züge steigt nur, wenn ein Zug ankommt, daher ist die verkehrsreichste Minute die Ankunftsminute eines Zuges. Zähle für jeden Zug i die Züge j, für die arrival[j] ≤ arrival[i] ≤ departure[j] gilt. Beide Vergleiche verwenden ≤, weil ein Zug auch in der Minute, in der er abfährt, noch auf seinem Bahnsteig steht.

Jeder der n Züge prüft alle n Züge, daher beträgt der Aufwand O(n²): 25 Millionen Paarprüfungen bei 5000 Zügen.

Algorithmus

Setze most = 0.
Zähle für jeden Zug i die Züge j, für die arrival[j] ≤ arrival[i] ≤ departure[j] gilt.
Wenn diese Anzahl größer als most ist, speichere sie.
Gib most zurück.

def minimumPlatforms(arrival, departure):
    n = len(arrival)
    most = 0
    for i in range(n):
        # trains standing at the station in the minute train i arrives
        here = 0
        for j in range(n):
            if arrival[j] <= arrival[i] <= departure[j]:
                here += 1
        most = max(most, here)
    return most

Sortiere beide Listen und durchlaufe sie mit zwei Zeigern

Idee

Die Anzahl der anwesenden Züge hängt nur davon ab, wie viele bis zu einer bestimmten Minute angekommen und wie viele abgefahren sind, nicht davon, welcher Zug wann abfährt. Sortiere daher die Ankunftszeiten und die Abfahrtszeiten als zwei unabhängige Listen. In zeitlicher Reihenfolge gelesen bilden sie die Ereignisse des Tages: Eine Ankunft fügt einen Zug hinzu, eine Abfahrt entfernt einen.

Bei gleichen Zeiten kommt die Ankunft zuerst, weil der abfahrende Zug seinen Bahnsteig in dieser Minute noch belegt. Im ersten Beispiel ist die Anzahl nach der Abfahrt um 1100 wieder 0, dann erfolgen die Ankünfte um 1500, 1520 und 1530 alle vor der Abfahrt um 1535, sodass die Anzahl 3 erreicht.

Sobald keine Ankünfte mehr übrig sind, können die verbleibenden Abfahrten die Anzahl nur noch verringern, also endet der Durchlauf dort. Das Sortieren kostet O(n log n) und der Durchlauf umfasst höchstens 2n Schritte.

Algorithmus

Sortiere eine Kopie von arrival und eine Kopie von departure.
Setze platforms, most, i und j auf 0.
Solange i < n: Wenn arrivals[i] ≤ departures[j], addiere 1 zu platforms, aktualisiere most und erhöhe i.
Andernfalls subtrahiere 1 von platforms und erhöhe j.
Gib most zurück.

def minimumPlatforms(arrival, departure):
    arrivals = sorted(arrival)
    departures = sorted(departure)
    n = len(arrivals)
    platforms = 0  # trains at the station right now
    most = 0
    i = 0  # next arrival
    j = 0  # next departure
    while i < n:
        if arrivals[i] <= departures[j]:
            # the next event is an arrival; on a tie the leaving train is still there
            platforms += 1
            most = max(most, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1
    return most

Stolperfallen und Grenzfälle

Vergleichen mit <, obwohl die inklusive Regel ≤ erfordert. Im zweiten Beispiel übernimmt dann jeder ankommende Zug den Bahnsteig des Zuges, der in derselben Minute abfährt, und die Antwort sinkt von 2 auf 1.
HHMM-Zahlen subtrahieren: 1300 minus 1259 ergibt 41, obwohl zwischen den Uhrzeiten eine Minute liegt. Ein Vergleich ist sicher, und die Lösung vergleicht nur.
Die Züge nach Ankunft sortieren und jeden nur mit dem Zug davor vergleichen. Ein langer Aufenthalt wie von 06:00 bis 22:00 im dritten Beispiel überschneidet sich mit Zügen weit unten in der Liste.
Züge überspringen, die in derselben Minute ankommen und abfahren. Vier Züge, die jeweils von 10:00 bis 10:00 stehen, benötigen vier Bahnsteige.

Häufige Fragen3

Wie hoch ist die zeitliche Komplexität des Problems mit der minimalen Anzahl an Bahnsteigen?

Das Sortieren der beiden Arrays kostet O(n log n) und der anschließende Durchlauf O(n), daher bestimmen die Sortiervorgänge den Aufwand. Die sortierten Kopien benötigen zusätzlichen Speicherplatz von O(n).

Worin unterscheidet sich „Minimum Platforms“ von „Meeting Rooms II“?

Bei beiden geht es um die größtmögliche Anzahl an Intervallen, die sich zu einem Zeitpunkt überschneiden. Hier belegt ein Zug seinen Bahnsteig noch bis zu der Minute, in der er abfährt; bei „Meeting Rooms II“ ist ein Raum genau dann frei, wenn sein Meeting endet. Beim Sweep entspricht das einem Vergleich: Bei Gleichstand verarbeitest du hier zuerst die Ankunft und dort zuerst das endende Meeting.

Kann das Problem der minimalen Bahnsteige ohne Sortieren gelöst werden?

Ja, da jede Zeit auf eine feste Uhrzeit abgebildet werden kann. Zähle die 2401 Indizes anhand der Zahl HHMM, addiere bei jeder Ankunft 1 und ziehe bei departure + 1 1 ab. Die größte laufende Summe ist die Antwort: Laufzeit O(n + 2400). Indizes wie 1260 bis 1299 sind keine Uhrzeiten und erhalten keine Ankunft, daher bilden sie nie einen Höchstwert.

def minimumPlatforms(arrival, departure):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

arrival = [900, 1500, 920, 1520, 1000, 1530]
departure = [930, 1600, 1010, 1535, 1100, 1545]

Erwartete Ausgabe