Задачі
Відрізки
Відрізки
Задано відрізки на прямій. Яку максимальну кількість відрізків можна вибрати так, щоб жодні два з них не перетинались? Відрізки вважаються відкритими.
Вхідні дані
У першому рядку задано кількість відрізків n~(1 \le n \le 10^5). У наступнихn рядках описано відрізки: i-ий рядок містить два цілих числа l_i та r_i~(1 \le l_i < r_i \le 10^9) — координати початку та кінця відрізка.
Вихідні дані
Виведіть максимальну кількість відрізків, що не перетинаються.
Приклад
Вхідні дані #1
5 1 4 3 8 7 8 2 5 4 6
Вихідні дані #1
3
Вхідні дані #2
4 1 3 2 6 1 8 2 5
Вихідні дані #2
1