Se citesc n intervale. Determinati, folosind metoda Greedy, numarul minim de intervale care trebuie eliminate astfel incat intervalele ramase sa nu se mai suprapuna doua cate doua (un interval care se termina exact cand incepe altul nu este considerat suprapunere).
- Date de intrare
- Pe prima linie se citeste n. Urmeaza n linii, fiecare cu doua numere: inceputul si sfarsitul unui interval.
- Date de iesire
- Se afiseaza un singur numar: numarul minim de intervale de eliminat.
- Restrictii
- 1 <= n <= 100000, 0 <= inceput < sfarsit <= 10^9
Exemple
Exemplul 1
Intrare
3 1 2 2 3 3 4
Iesire
0
Exemplul 2
Intrare
4 1 3 2 4 3 5 0 6
Iesire
2