Участник:Jzargo/Задача о покрытии отрезков точками

Материал из DISCOPAL
Перейти к: навигация, поиск

Ещё одна задача, которая лежит в "для решения", но на неё не получается сослаться: http://discopal.ispras.ru/Жадные_алгоритмы/Задача_о_покрытии_отрезков_точками

StasFomin 18:23, 15 мая 2019 (MSK): Ну странно это. Отлично можно сослаться.

Самое очевидное решение здесь:

  • 1. взять и упорядочить отрезки по левым концам
    • (отрезок = упорядоченная пара точек, одна из которых левая, а вторая правая. Т.е. у нас есть номер отрезка и два значения точек для него)
  • 2. Рассматриваем их поочереди. Отрезки, у которых точка - левый конец, добавляем в список рассматриваемых отрезков (изначально пустой). Если же конец правый и его нет в списке покрытых, то добавляем (покрываем) его, выписывая эту точку в ответ.

StasFomin 18:28, 15 мая 2019 (MSK): А напишите код на питоне, вы же можете. С примерными данными.


Для алгоритма легко показать контрпример, когда он не оптимален, но зато после каждой такой итерации покрытость рассмотренных отрезков сохраняется (и в конце покрыты все).

Сложность: O(n log n) - сортировка и O(n) - рассмотрение, значит итоговая: O(n log n)