Minimum Platforms

Q: Jaka jest złożoność czasowa problemu minimalnej liczby peronów?

Sortowanie dwóch tablic kosztuje O(n log n) , a następujące po nim przeglądanie O(n) , więc dominują sortowania. Posortowane kopie zajmują dodatkową pamięć O(n) .

Q: Czym różni się problem „minimum platform” od problemu „meeting rooms II”?

Oba zadania pytają o maksymalną liczbę przedziałów nakładających się na siebie w jednej chwili. Tutaj pociąg zajmuje peron do minuty, w której odjeżdża; w zadaniu „meeting rooms II” sala jest wolna w chwili zakończenia spotkania. W algorytmie przemiatania sprowadza się to do jednego porównania: przy remisie najpierw obsługujesz przyjazd, a w drugim zadaniu — kończące się spotkanie.

Q: Czy problem minimalnej liczby platform można rozwiązać bez sortowania?

Tak, ponieważ każda godzina mieści się w stałym zakresie zegara. Utwórz 2401 liczników indeksowanych liczbą HHMM , dodaj 1 przy każdym przybyciu i odejmij 1 przy departure + 1 . Największa suma narastająca jest odpowiedzią: czas O(n + 2400) . Indeksy takie jak 1260–1299 nie są godzinami na zegarze i nie przypada na nie żadne przybycie, więc nigdy nie wyznaczają maksimum.

ŚrednieSortowanie Algorytmy zachłanne Dwa wskaźniki

+10

Stacja ma rozkład jazdy na jeden dzień: pociąg i przyjeżdża o arrival[i] i odjeżdża o departure[i]. Godziny są zapisane jako liczby w formacie HHMM, czyli czas bez dwukropka, więc 930 oznacza 09:30.

Pociąg zajmuje peron od minuty przyjazdu do minuty odjazdu włącznie. Dlatego pociąg przyjeżdżający w tej samej minucie, w której odjeżdża inny pociąg, nie może zająć jego peronu.

Zwróć minimalną liczbę peronów, jakich potrzebuje stacja, aby żaden pociąg nie musiał czekać.

Funkcja

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

arrivalinteger-array: godzina przyjazdu każdego pociągu w formacie liczby HHMM
departureinteger-array: godzina odjazdu każdego pociągu w postaci liczby HHMM; departure[i] odpowiada arrival[i]
Zwracainteger: największa liczba pociągów na stacji w tej samej minucie, czyli minimalna liczba wymaganych peronów

Ograniczenia

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
Każda godzina w formacie HHMM jest prawidłowa: jej dwie ostatnie cyfry mają wartość najwyżej 59.
Wszystkie pociągi kursują tego samego dnia. Tablice nie są posortowane.

Przykłady

Wejście: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
Wyjście: 3
Wyjaśnienie: O 15:30 na stacji stoją trzy pociągi: te kursujące od 15:00 do 16:00, od 15:20 do 15:35 i od 15:30 do 15:45. W żadnej minucie nie ma czterech pociągów, więc wystarczą 3 perony.

Wejście: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
Wyjście: 2
Wyjaśnienie: Pociąg przyjeżdżający o 12:30 spotyka się z pociągiem odjeżdżającym o 12:30. To samo dzieje się o 13:00. W każdej z tych minut na stacji są dwa pociągi, więc odpowiedź to 2, a nie 1.

Wejście: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
Wyjście: 2
Wyjaśnienie: Pociąg kursujący od 06:00 do 22:00 zajmuje jeden peron przez cały dzień. Pociągi kursujące od 07:00 do 07:15 i od 13:00 do 14:00 nigdy się nie spotykają, więc korzystają z drugiego peronu: 2.

Pytanie dodatkowe

Niektóre pociągi nocne przyjeżdżają przed północą i odjeżdżają po niej, więc ich numer odjazdu jest mniejszy niż numer przyjazdu. Jak policzyć perony, gdy rozkład jazdy przechodzi przez północ?

Rozwiązanie

Odpowiedzią jest największa liczba pociągów na stacji w tej samej minucie. Zadanie polega na znalezieniu tej najbardziej ruchliwej minuty bez porównywania każdej pary pociągów. Posortuj osobno przyjazdy i odjazdy, a następnie przejdź raz przez wydarzenia z całego dnia, śledząc bieżącą liczbę pociągów — w ten sposób znajdziesz wynik w O(n log n).

Policz pociągi przy każdym przyjeździe

Poprawne, ale nie kończy się na największych testach

Intuicja

Pociągi stojące w tej samej minucie potrzebują różnych peronów, więc najbardziej ruchliwa minuta stanowi dolną granicę. To również wystarczy: otwieraj nowy peron tylko wtedy, gdy przyjeżdżający pociąg zastaje wszystkie otwarte perony zajęte. W tej minucie na każdym otwartym peronie stoi pociąg, a na nowym peronie stanie kolejny, więc nigdy nie otworzysz więcej peronów niż wynosi szczytowe zapotrzebowanie.

Liczba obecnych pociągów zwiększa się tylko wtedy, gdy przyjeżdża pociąg, więc najbardziej ruchliwa minuta jest minutą przyjazdu któregoś z pociągów. Dla każdego pociągu i policz pociągi j, dla których zachodzi arrival[j] ≤ arrival[i] ≤ departure[j]. Oba porównania używają ≤, ponieważ pociąg nadal stoi na swoim peronie w minucie odjazdu.

Każdy z n pociągów sprawdza wszystkie n pociągów, więc złożoność obliczeniowa wynosi O(n²): 25 milionów porównań par dla 5000 pociągów.

Algorytm

Ustaw most = 0.
Dla każdego pociągu i policz pociągi j, dla których arrival[j] ≤ arrival[i] ≤ departure[j].
Jeśli ta liczba jest większa niż most, zapisz ją.
Zwróć most.

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

Posortuj obie listy i przejdź przez nie, używając dwóch wskaźników

Intuicja

Liczba obecnych pociągów zależy wyłącznie od tego, ile pociągów przyjechało i ile odjechało do danej minuty, a nie od tego, który pociąg odjeżdża kiedy. Posortuj więc czasy przyjazdów i czasy odjazdów jako dwie niezależne listy. Odczytane razem w porządku chronologicznym tworzą wydarzenia danego dnia: przyjazd dodaje pociąg, a odjazd go usuwa.

W przypadku remisu najpierw następuje przyjazd, ponieważ odjeżdżający pociąg nadal zajmuje swój peron w tej minucie. W pierwszym przykładzie liczba pociągów wraca do 0 po odjeździe o 1100, a następnie przyjazdy o 1500, 1520 i 1530 następują przed odjazdem o 1535, więc liczba pociągów osiąga 3.

Gdy skończą się przyjazdy, pozostałe odjazdy mogą już tylko zmniejszać liczbę pociągów, więc przechodzenie przez listę kończy się w tym miejscu. Sortowanie wymaga O(n log n), a przejście przez listę zajmuje co najwyżej 2n kroków.

Algorytm

Posortuj kopię arrival i kopię departure.
Ustaw platforms, most, i i j na 0.
Dopóki i < n: jeśli arrivals[i] ≤ departures[j], dodaj 1 do platforms, zaktualizuj most i przesuń i dalej.
W przeciwnym razie odejmij 1 od platforms i przesuń j dalej.
Zwróć most.

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

Pułapki i przypadki brzegowe

Porównywanie za pomocą <, gdy warunek włącznie wymaga ≤. W drugim przykładzie każdy przyjeżdżający pociąg zajmuje wtedy peron pociągu odjeżdżającego w tej samej minucie, a wynik spada z 2 do 1.
Odejmowanie liczb HHMM: 1300 minus 1259 to 41, chociaż te godziny dzieli jedna minuta. Ich porównywanie jest bezpieczne, a rozwiązanie wykonuje tylko porównania.
Sortowanie pociągów według czasu przyjazdu i porównywanie każdego z nich tylko z poprzednim pociągiem. Długi postój, taki jak od 06:00 do 22:00 w trzecim przykładzie, nakłada się na pociągi znajdujące się daleko na liście.
Pomijanie pociągów, które przyjeżdżają i odjeżdżają w tej samej minucie. Cztery pociągi stojące od 10:00 do 10:00 potrzebują czterech peronów.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu minimalnej liczby peronów?

Sortowanie dwóch tablic kosztuje O(n log n), a następujące po nim przeglądanie O(n), więc dominują sortowania. Posortowane kopie zajmują dodatkową pamięć O(n).

Czym różni się problem „minimum platform” od problemu „meeting rooms II”?

Oba zadania pytają o maksymalną liczbę przedziałów nakładających się na siebie w jednej chwili. Tutaj pociąg zajmuje peron do minuty, w której odjeżdża; w zadaniu „meeting rooms II” sala jest wolna w chwili zakończenia spotkania. W algorytmie przemiatania sprowadza się to do jednego porównania: przy remisie najpierw obsługujesz przyjazd, a w drugim zadaniu — kończące się spotkanie.

Czy problem minimalnej liczby platform można rozwiązać bez sortowania?

Tak, ponieważ każda godzina mieści się w stałym zakresie zegara. Utwórz 2401 liczników indeksowanych liczbą HHMM, dodaj 1 przy każdym przybyciu i odejmij 1 przy departure + 1. Największa suma narastająca jest odpowiedzią: czas O(n + 2400). Indeksy takie jak 1260–1299 nie są godzinami na zegarze i nie przypada na nie żadne przybycie, więc nigdy nie wyznaczają maksimum.

def minimumPlatforms(arrival, departure):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik