Funkcjonowanie firmy przewozowej nie jest takie proste, bla bla bla... Mając daną listę wszystkich kursów zaplanowanych na jutro, musisz tak zaplanować rozkład jazdy taksówek, aby wykorzystać minimalną ilość samochodów. Dla uproszczenia zakładamy, że adres da się zapisać w postaci pary liczb (a, b). Czas przejazdu z (a, b) do (c, d) jest równy |a-c|+|b-d| minut. Dany taksówkarz może wykonać dany kurs wtedy, gdy jest to jego pierwszy kurs lub gdy po wykonaniu poprzedniego zdąży dojechać na miejsce startu co najmniej minutę przed planowanym czasem odjazdu.
W pierwszej lini znajduje się liczba zaplanowanych przejazdów n<=500. W kolejnych n wierszach znajdują się opisy kolejnych kursów. Każdy kurs jest opisany przez czas odjazdu w formacie hh:mm (od 00:00 do 23:59) oraz dwie pary liczb określające adres początkowy i końcowy. Wszystkie liczby są w przedziale od 0 do 200. Lista jest posortowana w kolejności rosnących czasów odjazdu. Twój program powinien wypisać minimalną liczbę taksówek potrzebną do wykonania wszystkich zleceń w terminie.
Dla danych wejściowych
2 08:00 10 11 9 16 08:07 9 16 10 11
Poprawnym wynikiem jest:
1
Dla danych wejściowych
2 08:00 10 11 9 16 08:06 9 16 10 11
Poprawnym wynikiem jest:
2
[Zgłoś rozwiązanie] [Moje zgłoszenia]