Rezerwacja sal wykładowcych
Limit pamięci: 32 MB
Rozporządzamy jedną salą wykładową.
Wykładowcy, którzy chcą korzystać z sali, składają zamówienia określając czas rozpoczęcia i zakończenia wykładu.
Układamy plan wykorzystania sali akceptując pewne wykłady i odrzucając inne, tak aby czas wykorzystania sali był jak najdłuższy.
Zakładamy, że w momencie zakończenia jednego wykładu może się rozpocząć następny wykład.
Zadanie
Napisz program, który:
- wczytuje ze standardowego wejścia zamówienia wykładowców,
- oblicza maksymalny czas wykorzystania sali (przy odpowiednio ułożonym planie wykładów),
- zapisuje wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodatnia
(
).
Jest to liczba zamówień.
W każdym z kolejnych
wierszy są zapisane dwie liczby całkowite
oraz
, oddzielone pojedynczym odstępem,
spełniające nierówności
.
Jest to zamówienie na salę wykładową w otwartym przedziale czasu od
do
(wykładowca potrzebuje sali w czasie reprezentowanym na osi czasu przez odcinek otwarty).
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia należy zapisać maksymalny czas wykorzystania sali.
Przykład
Dla danych wejściowych:
12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20
poprawną odpowiedzią jest:
16
Autor zadania: Wojciech Guzicki.