ПОМОГИТЕ РЕШИТЬ ЗАДАЧУ В PYTHON!

Question

ПОМОГИТЕ РЕШИТЬ ЗАДАЧУ В PYTHON!

Umar Ahmetianov Ученик (84), на голосовании 2 месяца назад

Решая задачу из контрольной по математике, Вася получил ответ в виде объединения N
отрезков [Li,Ri]
на числовой прямой. Однако, некоторые из этих отрезков могут пересекаться друг с другом, что не слишком нравится Васе. Ваша задача — представить Васин ответ в виде объединения минимального количества отрезков.

Входные данные
В первой строке указано число N
(1⩽N⩽50000)
. В следующих N
строках перечислены пары целых чисел Li
и Ri
(|Li|,|Ri|⩽50000)
, каждая пара с новой строки, числа в парах отделены друг от друга одним или несколькими пробелами.

Выходные данные
В первой строке выведите число M
— количество отрезков в искомом объединении. В следующих M
строках выведите сами эти отрезки в том же формате, что и во входном файле. Список отрезков необходимо упорядочить по возрастанию левого конца.

Надо решить задачу методом сканирующей прямой.

Answer 1

Задачи на интервалы решаются сортировкой координат, и перебором подряд от меньших к большим, считая «текущее» кол-во активных.
Напр., даны отрезки [1,5], [2,3], [3,9]
Тут ещё важно, каковы крайние точки - для простоты считаем, что все края «включены».
Сортируем координаты, не забывая, где какая - одни из них точки входа (in), другие - выхода (out):
1 i
2 i
3 o
3 i
5 o
9 o
Изначально кол-во включённых слоёв 0. Когда "i" добавляем 1, когда "o" – вычитаем. Пошли:
- - 0
1 i 1 - начался нужный отрезок - в результат добавим [1, ?
2 i 2 - != 1, закончился – в результат добавили [1,2]
3 o 1 - снова начался нужный
3 i 2 - и тут же закончился, ничего не делаем
5 o 1 - начался нужный [5, ?
9 o 0 - закончился, в результат добавили [5,9]
Результат: [1,2], [5,9]. Складываем длины 1+4 = 5. Ответ: 5