Контест Junior Интервалы спрашивают часто обновлено
Объединить отрезки и найти покрытую длину
Условие
Даны n отрезков [l, r] на прямой (концы включительно, отрезок может быть точкой). Объедините все пересекающиеся и касающиеся отрезки (у [1, 3] и [3, 5] общая точка, они сливаются; [1, 2] и [3, 4] нет). Выведите число получившихся отрезков и их суммарную длину (длина [l, r] равна r − l).
Ввод: в первой строке n (1 ≤ n ≤ 2500), далее n строк l r (0 ≤ l ≤ r ≤ 10⁹).
Вывод: два числа: количество отрезков после объединения и их суммарная длина.
Пример 1
Ввод:
4
1 3
2 6
8 10
10 12
Вывод:
2 9
Пример 2
Ввод:
2
1 2
3 4
Вывод:
2 2
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.