Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Jasio ma niebywałe wzięcie u dziewczyn. Umówił się z wieloma z nich na randki i różne dziwne zabawy, których prawdopodobnie i tak nie zrozumiesz, skoro czytasz to zadanie. Problem polega na tym, że Jasio nie jest zbyt rozgarnięty i umawiał się na randki nie bacząc na terminy, a zatem zachodzi ryzyko, że niektóre randki trzeba będzie odwołać. Jasio chciałby wybrać randki, na które pójdzie w taki sposób, aby przedziały czasu trwania randek były parami rozłączne oraz aby zmaksymalizować liczbę randek, na których będzie. Pomóż mu, a może zdradzi Ci sekret jak też mieć takie powodzenie u kobiet.
Napisz program, który: wczyta informacje o zaplanowanych randkach, wyznaczy maksymalną liczbę randek, na które Jasio może pójść i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę zaplanowanych randek. W kolejnych N wierszach znajdują się opisy kolejnych randek. Opis każdej z nich składa się z dwóch liczb naturalnych Si, Ei, oddzielonych pojedynczym odstępem, określających początek i koniec przedziału czasu, w którym trwa randka.
Wyjście
W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – maksymalna liczba randek, które może odbyć Jasio.
Ograniczenia
1 ≤ N ≤ 200 000, 0 ≤ Si ≤ Ei ≤ 109.
Przykład
| Input | Output | |
|
|