Se citesc n intervale. Determinati, folosind o strategie Greedy (sortare urmata de o singura parcurgere), reuniunea acestor intervale sub forma unui numar minim de intervale disjuncte care sa acopere exact aceleasi puncte ca reuniunea intervalelor initiale (doua intervale care se ating intr-un punct se unesc intr-unul singur).
- 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 intervalele rezultate in urma reuniunii, in ordine crescatoare, cate unul pe linie, sub forma 'inceput sfarsit'.
- Restrictii
- 1 <= n <= 100000, 0 <= inceput <= sfarsit <= 10^9
Exemple
Exemplul 1
Intrare
4 1 3 2 6 8 10 15 18
Iesire
1 6 8 10 15 18
Exemplul 2
Intrare
3 1 4 4 5 7 8
Iesire
1 5 7 8