Se citesc n intalniri, fiecare cu un moment de inceput si unul de sfarsit. Determinati, folosind metoda Greedy, numarul minim de sali necesare astfel incat toate intalnirile sa poata avea loc, fara ca doua intalniri suprapuse in timp sa foloseasca aceeasi sala (o intalnire care se termina exact cand incepe alta poate folosi aceeasi sala).
- Date de intrare
- Pe prima linie se citeste n. Urmeaza n linii, fiecare cu doua numere: inceputul si sfarsitul unei intalniri.
- Date de iesire
- Se afiseaza un singur numar: numarul minim de sali necesare.
- Restrictii
- 1 <= n <= 100000, 0 <= inceput < sfarsit <= 10^9
Exemple
Exemplul 1
Intrare
3 1 2 2 3 3 4
Iesire
1
Exemplul 2
Intrare
3 1 4 2 5 3 6
Iesire
3