Se citesc n activitati, fiecare caracterizata printr-un moment de inceput si unul de sfarsit. Doua activitati sunt compatibile daca intervalele lor nu se suprapun (o activitate care se termina exact cand incepe alta este considerata compatibila cu aceasta). Determinati, folosind metoda Greedy, numarul maxim de activitati compatibile doua cate doua ce pot fi selectate.
- Date de intrare
- Pe prima linie se citeste n. Urmeaza n linii, fiecare cu doua numere: momentul de inceput si cel de sfarsit al unei activitati.
- Date de iesire
- Se afiseaza un singur numar: numarul maxim de activitati compatibile.
- Restrictii
- 1 <= n <= 100000, 0 <= inceput < sfarsit <= 10^9
Exemple
Exemplul 1
Intrare
3 1 2 2 3 3 4
Iesire
3
Exemplul 2
Intrare
4 1 3 2 4 3 5 0 6
Iesire
2