Ile potrzeba peronów?
Zadanie
Stacja wymaga poprawek tak, aby żaden pociąg nie oczekiwał na peron. Na podstawie rozkładu pociągów na danej stacji określ ile potrzeba minimalnie peronów, aby w dowolnym momencie każdy pociąg miał swój peron, gdy stoi na stacji. Zakładamy, że podany rozkład jest prawidłowy.
Przykład
Rano na stację przyjeżdża wiele pociągów. Przyjrzyjmy się rozkładowi w okolicach godziny 8:00
| Przyjazd | Odjazd |
|---|---|
| 07:00 | 07:15 |
| 07:10 | 07:20 |
| 07:15 | 07:35 |
| 07:25 | 08:00 |
| 07:30 | 07:50 |
| 07:35 | 08:05 |
| 07:40 | 08:00 |
Pociągi nie będą oczekiwać na peron jeśli na stacji będą 4 perony co przedstawia poniższy graf:
Jak można odczytać z grafu od 07:00 do 07:30 wystarczyłyby tylko dwa perony, ale jednak później potrzebne są dwa dodatkowe perony, aby wszystkie pociągi mogły stać równocześnie.
Algorytm
W celu znalezienie ile peronów stacja musi posiadać warto się zastanowić co to znaczy "pociąg wjechał na stację" i "pociąg opuścił stację". Ten pierwszy oznacza, że pociąg wymaga peronu, więc należy zmienną zliczającą ilość peronów zwiększyć o 1, a w drugim przypadku opuszczenie stacji oznacza zmniejszenie ilości potrzebnych peronów.
W tym konkretnym zadaniu nie interesuje nas kolejność wjazdów i wyjazdów, więc czasy przyjazdu i odjazdu możemy posortować rosnąco. Algorytm w każdym kolejnym kroku, dopóki ma przyjechać jakikolwiek pociąg sprawdza co nastąpi szybciej: przyjazd kolejnego pociągu czy odjazd już znajdującego się na stacji. Po dokonaniu należy zaktualizować odpowiednio ilość potrzebnych peronów oraz rozkład. Za każdym razem należy sprawdzić czy nowa liczba peronów nie jest większa od aktualnego maksimum. Jeśli tak jest to maksimum należy zaktualizować.
Bardzo ważne, aby pamiętać, że najpierw należy obsłużyć odjazd, a następnie przyjazd pociągu. Dla przedstawionego przykładu na peronie pierwszym pociągi nonstop się wymieniają i jeśli najpierw doliczy się potrzebny peron zanim zostanie "zwolniony" to program może podac jako odpowiedź wartość o co najmniej 1 większą niż należy.
Przykład
Wróćmy do rozkładu podanego wcześniej. Tym razem jednak posortujmy czasy odjazdów i przyjazdów:
| Przyjazd | 07:00, 07:10, 07:15, 07:25, 07:30, 07:35, 07:40 |
|---|---|
| Odjazd | 07:15, 07:20, 07:35, 07:50, 08:00, 08:00, 08:05 |
Jeśli rozkład jest prawidłowy to wpierw powinien nastąpić przyjazd pociągu.
| Peronów | Naj. Przyjazd | Naj. Odjazd | Komentarz |
|---|---|---|---|
| 0 | 07:00 | 07:15 | Przyjazd jest mniejszy od odjazdu, więc zwiększamy ilość potrzebnych peronów |
| 1 | 07:10 | 07:15 | Przyjazd szybciej, więc potrzebny kolejny peron |
| 2 | 07:15 | 07:15 | Następuje odjazd i przyjazd, więc ilość peronów nie ulega zmianie |
| 2 | 07:25 | 07:20 | Szybciej odjazd niż przyjazd zmniejszamy zapotrzebowanie |
| 1 | 07:25 | 07:35 | Pierwszy przyjazd następnego pociągu |
| 2 | 07:30 | 07:35 | Kolejny peron potrzebny dla kolejnego pociągu |
| 3 | 07:35 | 07:35 | Wymiana pociągów na stacji, ilość potrzebnych peronów nie zmienia się |
| 3 | 07:40 | 07:50 | Kolejny pociąg wjeżdża na stację |
| 4 | - | 07:50 | Pociąg opuszcza stację |
| 3 | - | 08:00 | Pociąg opuszcza stację |
| 2 | - | 08:00 | Pociąg opuszcza stację |
| 1 | - | 08:05 | Ostatni pociąg opuszcza stację |
| 0 | - | - | Koniec rozkładu |
Powyżej został przedstawiony pełny opis sytuacji na stacji. Algorytm mógłby skończyć obliczenia kiedy według rozkładu żaden z pociągów więcej nie wjedzie na stację. Jeśli wiadomo, że od pewnego momentu pociągi tylko opuszczają stację to na pewno maksimum nie zostanie zmienione.
Implementacja
Ile stacji?
Poniższa funkcja ileStacji() realizuje działanie algorytmu dla podanych czasów odjazdów oraz przyjazdów pociągu. W wyniku otrzymuje się liczbę całkowitą, która określa ile potrzeba minimalnie peronów na stacji. Zakładamy, że czas przyjazdu lub odjazdu to liczba całkowita postaci hhmm czyli np. 07:35 to 735, a 12:12 to 1212.
- def ileStacji(przyjazdy, odjazdy):
- przyjazdy.sort()
- odjazdy.sort()
- teraz, max = 0, 0
- while (len(przyjazdy) > 0):
- if (przyjazdy[0] < odjazdy[0]):
- przyjazdy.pop(0)
- teraz += 1
- if (teraz > max):
- max = teraz
- else:
- odjazdy.pop(0)
- teraz -= 1
- return max
(2. - 3.) Najpierw otrzymane dane należy posortować i (4.) zanicjalizować dwie zmienne teraz - aktualna ilość używanych peronów oraz max - dotychczas najwyższa ilość potrzebnych peronów. Następnie (5.) dopóki ma przyjechać jakiś pociąg to (6.) sprawdź czy przyjazd nastąpi przed odjazdem. Jeśli tak to (7.) usuń najbliższy czas przyjazdu, (8.) zwiększ zapotrzebowanie na perony i (9. - 10.) zaktualizuj maksimum potrzebnych peronów jeśli istnieje taka potrzeba. Jeśli jednak pierwszy będzie odjazd to (11.) usuń pierwszy czas odjazdu i (12.) zwolnij peron. Na koniec (13.) zwróć znalezione maksimum.
Testowanie funkcji
W celu przetestowania napisanej funkcji można skorzystać z poniższego kodu.
- n = int(input("Ile przyjazdów?\n n = "))
- print("Podaj czas przyjazdu i odjazdu każdego pociągu")
- przyjazdy, odjazdy = [], []
- while(n > 0):
- data = [int(x) for x in input().split()]
- przyjazdy.append(data[0])
- odjazdy.append(data[1])
- n -= 1
- print(ileStacji(przyjazdy, odjazdy))
Oto przykładowy zestaw danych dla którego poprawną odpowiedzią jest 4.
- 7
- 0700 0715
- 0710 0720
- 0715 0735
- 0725 0800
- 0730 0750
- 0735 0805
- 0740 0800
Zadania
Zadanie 1
Napisz program, który uwzględni, że po czasie odjazdu pociągu, a przyjazdem kolejnego musi zostać zachowany bufor 5 minut. Oznacza to, że po rozkładowym odjeździe na peron inny pociag będzie mógł wjechać dopiero za 5 minut.
Dodanie 5 minutowego buforu (oznaczony czerwonym krzyżykiem) do aktualnego rozkładu jazdy powoduje, że rozkład pociagów na stacjach przedstawia się następująco:
Jak widać w tym przypadku udało się rozmieścić wszystkie pociągu ponownie na czterech peronach, ale mogłoby się zdarzyć, że potrzebny byłby dodatkowy peron.