Жадные алгоритмы/Задача о покрытии отрезков точками — различия между версиями

Версия 20:52, 6 октября 2014

Маркеева Лариса 973б
Пусть все наши N отрезков представлены парами {left, id}, {right, id}. Где left - координата левого конца, right - координата правого конца, id - "номер" нашего отрезка.
Так же, очевидно, что нам нужно как-то отмечать уже покрытые отрезки. Для этого заведем булевый массив flags[1..N], который изначально содержит все значения false.
Так же заведем LIFO очередь для хранения рассматриваемых в данный момент вершин.
И массив для хранения ответов.
Все пары наших отрезков {left, id}, {right, id} будут храниться в массиве.
Отсортируем его по возрастанию координат отрезков. При чем, если у нас встречается "правая" и "левая" часть с одинаковой координатой, сначала в отсортированном массиве пойдет "левая", потом "правая".
Данная операция займет минимум O(N*Log(N)) - если значение N неизвестно, или O(N)- если значение N известно.

Начинаем обход нашего массива:

Если мы встретили левый конец отрезка -> добавляем его в LIFO очередь.

Если мы встретили правый конец:

Если в нашем массиве flags отрезок с этим id помечен как покрытый, ничего не делаем, пропускаем эту запись.

Если в нашем массиве flags отрезок с этим id помечен как непокрытый, то добавляем координату его правого конца в ответ. Очевидно, что в нашей LIFO есть только "левые" части отрезков -> все они покрылись только что добавленной в ответ точкой. Поэтому, мы просто выталкиваем все "левые" концы из очереди, помечая их отрезки как покрытые.

И так до самого конца массива.

Т.к. мы просматриваем все элементы массива. Всего записей в массиве 2N. А так же тратим время на заталкивание/выталкивание из нашей LIFO очереди. В худшем случае в нее можно затолкать N элементов и N вытолкнуть(левых частей N штук), следовательно, времени на работу со стеком потратиться не более 2N. Поэтому количество операций не превосходит 4N.
Следовательно, мы имеем сложность O(N) на обход.

Таким образом, алгоритм будет работать или O(NlogN) или O(N) в зависимости от того, какая сортировка будет применена к массиву.