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

Pociągi nie będą oczekiwać na peron jeśli na stacji będą 4 perony co przedstawia poniższy graf:

Zajętość peronów

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:

Jeśli rozkład jest prawidłowy to wpierw powinien nastąpić przyjazd pociągu.

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.

1. int ileStacji(vector<int> przyjazdy, vector<int> odjazdy) {
2.   sort(przyjazdy.begin(), przyjazdy.end());
3.   sort(odjazdy.begin(), odjazdy.end());
4.   for (int i = 0; i < odjazdy.size(); i++)
5.     odjazdy[i] += 5;
6.   int teraz = 0, max = 0;
7.   while (przyjazdy.size() > 0) {
8.     if (przyjazdy[0] < odjazdy[0]) {
9.       przyjazdy.erase(przyjazdy.begin());
10.       teraz++;
11.       if (teraz > max)
12.         max = teraz;
13.     }
14.     else {
15.       odjazdy.erase(odjazdy.begin());
16.       teraz--;
17.     }
18.   }
19.   return max;
20. }

(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 (15.) zwróć znalezione maksimum.

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniższego kodu.

1. int main() {
2.   vector<int> przyjazdy, odjazdy;
3.   int n, a, b;
4.   cout << "Ile przyjazdow?\n n = ";
5.   cin >> n;
6.   cout << "Podaj czas przyjazdu i odjazdu kazdego pociagu\n";
7.   while (n > 0) {
8.     cin >> a >> b;
9.     przyjazdy.push_back(a);
10.     odjazdy.push_back(b);
11.     n--;
12.   }
13.   cout << ileStacji(przyjazdy, odjazdy) << endl;
14.   system("pause");
15.   return 0;
16. }

Oto przykładowy zestaw danych dla którego poprawną odpowiedzią jest 4.

1. 7
2. 0700 0715
3. 0710 0720
4. 0715 0735
5. 0725 0800
6. 0730 0750
7. 0735 0805
8. 0740 0800

• Kod źródłowy Implementacja

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:

Zajętość peronów z 5 minutowym buforem

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.

• Kod źródłowy Zadanie 1