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.