Zadanie : infor-3-3
Zadanie

Rozważamy przedziały domknięte liczb całkowitych. Każdy taki przedział można opisać parą liczb całkowitych [a, b], a ≤ b, w której a oznacza początek przedziału, natomiast b jest jego końcem.

Do przedziału [a, b] należą wszystkie liczby całkowite c spełniające nierówność a ≤ c ≤ b. Liczbę b – a + 1 nazywamy długością przedziału.

Dla dwóch przedziałów P i Q mówimy, że P zawiera się w Q, gdy każda liczba z należąca do przedziału P należy także do przedziału Q. O przedziale Q mówimy wtedy, że zawiera przedział P.

Łańcuchem przedziałów nazywamy każdy skończony ciąg przedziałów P1, P2, …, Pk, w którym każdy przedział o numerze większym od 1 zawiera przedział go poprzedzający w tym ciągu. Liczbę k nazywamy długością łańcucha.

Przykład:

Rozważmy 6 przedziałów: A = [-2,4], B = [-4,3], C = [-3,6], D = [0,3], E = [1,1], F = [7,9]. Przedział A ma długość 7. Przedział C zawiera przedział A, natomiast przedziały E, D, A, C tworzą łańcuch o długości 4.

Napisz program, który obliczy długość najdłuższego łańcucha przedziałów, który można utworzyć z podanych przedziałów.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą n z zakresu 1..2000.

W każdym z kolejnych n wierszy wejścia zapisano dwie liczby całkowite z zakresu -2000..2000, które są odpowiednio początkiem i końcem przedziału.

Wszystkie podane przedziały są różne, tzn. każdy dowolnie wybrany przedział występuje na wejściu co najwyżej raz.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać obliczoną maksymalną długość łańcucha.

Przykład

Dla danych podanych na wejściu:

4
-7 7
5 8
-4 -2
-9 -2

Poprawną odpowiedzią jest wyjście:

2

Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5

Opcje zadania:

Biblioteki         : iostream iomanip cmath string 
Limit czasu        : 0.1 s
Limit pamięci      : 32 MB
Słowa niedozwolone :