Задача о покрытии отрезков точками

Дано N отрезков на прямой. Требуется покрыть их наименьшим числом точек, т.е. найти наименьшее множество точек такое, что каждому отрезку принадлежит хотя бы одна точка.

Также рассмотрим усложнённый вариант этой задачи - когда дополнительно указано "запрещённое" множество отрезков, т.е. никакая точка из ответа не должна принадлежать ни одному запрещённому отрезку.

Следует также заметить, что эту задачу можно рассматривать и как задачу в теории расписаний - требуется покрыть заданный набор мероприятий-отрезков наименьшим числом точек.

Ниже будет описан жадный алгоритм, решающий обе задачи за O (N log N).

Решение первой задачи

Заметим сначала, что можно рассматривать только те решения, в которых каждая из точек находится на правом конце какого-либо отрезка. Действительно, нетрудно понять, что любое решение, если оно не удовлетворяет этому свойству, можно привести к нему, сдвигая его точки вправо настолько, насколько это возможно.

Попытаемся теперь построить решение, удовлетворяющее указанному свойству. Возьмём точки-правые концы отрезков, отсортируем их, и будем двигаться по ним слева направо. Если текущая точка является правым концом уже покрытого отрезка, то мы пропускаем её. Пусть теперь текущая точка является правым концом текущего отрезка, который ещё не был покрыт до этого. Тогда мы должны добавить в ответ текущую точку, и отметить все отрезки, которым принадлежит эта точка, как покрытые. Действительно, если бы мы пропустили текущую точку и не стали бы добавлять её в ответ, то, так как она является правым концом текущего отрезка, то мы уже не смогли бы покрыть текущий отрезок.

Однако при наивной реализации этот метод будет работать за O (N²). Опишем эффективную реализацию этого метода.

Возьмём все точки-концы отрезков (как левые, так и правые) и отсортируем их. При этом для каждой точки сохраним вместе с ней номер отрезка, а также то, каким концом его она является (левым или правым). Кроме того, отсортируем точки таким образом, что, если есть несколько точек с одной координатой, то сначала будут идти левые концы, и только потом - правые. Заведём стек, в котором будут храниться номера отрезков, рассматриваемых в данный момент; изначально стек пуст. Будем двигаться по точкам в отсортированном порядке. Если текущая точка - левый конец, то просто добавляем номер её отрезка в стек. Если же она является правым концом, то проверяем, не был ли покрыт этот отрезок (для этого можно просто завести массив булевых переменных). Если он уже был покрыт, то ничего не делаем и переходим к следующей точке (забегая вперёд, мы утверждаем, что в этом случае в стеке текущего отрезка уже нет). Если же он ещё не был покрыт, то мы добавляем текущую точку в ответ, и теперь мы хотим отметить для всех текущих отрезков, что они становятся покрытыми. Поскольку в стеке как раз хранятся номера непокрытых ещё отрезков, то будем доставать из стека по одному отрезку и отмечать, что он уже покрыт, пока стек полностью не опустеет. По окончании работы алгоритма все отрезки будут покрыты, и притом наименьшим числом точек (повторимся, здесь важно требование, что при равенстве координат сначала идут левые концы, и только затем правые).

Таким образом, весь алгоритм выполняется за O (N), не считая сортировки точек, а итоговая сложность алгоритма как раз равна O (N log N).

Решение второй задачи

Здесь уже появляются запрещённые отрезки, поэтому, во-первых, решения вообще может не существовать, а во-вторых, уже нельзя утверждать, что ответ можно составить только из правых концов отрезков. Однако описанный выше алгоритм можно соответствующим образом модифицировать.

Снова возьмём все точки-концы отрезков (как целевых отрезков, так и запрещённых), отсортируем их, сохранив вместе с каждой точкой её тип и отрезок, концом которого она является. Опять же, отсортируем отрезки так, чтобы при равенстве координат левые концы шли перед правыми, а если и типы концов равны, то левые концы запрещённых должны идти перед левыми концами целевых, а правые концы запрещённых - после целевых (чтобы запрещённые отрезки учитывались как можно дольше при равенстве координат). Заведём счётчик запрещённых отрезков, который будет равен числу запрещённых отрезков, покрывающих текущую точку. Заведём очередь (queue), в которой будут храниться номера текущих целевых отрезков. Будем перебирать точки в отсортированном порядке. Если текущая точка - левый конец целевого отрезка, то просто добавим номер её отрезка в очередь. Если текущая точка - правый конец целевого отрезка, то, если счётчик запрещённых отрезков равен нулю, то мы поступаем аналогично предыдущей задаче - ставим точку в текущую точку, и выталкиваем все отрезки из очереди, отмечая, что они покрыты. Если же счётчик запрещённых отрезков больше нуля, то в текущую точку мы стрелять не можем, а потому мы должны найти самую последнюю точку, свободную от запрещённых отрезков; для этого надо поддерживать соответствующий указатель last_free, который будет обновляться при поступлении запрещённых отрезков. Тогда мы стреляем в last_free-EPS (потому что прямо в неё нельзя стрелять - эта точка принадлежит запрещённому отрезку), и выталкивать отрезки из очереди, пока точка last_free-EPS принадлежит им. А именно, если текущая точка - левый конец запрещённого отрезка, то мы увеличиваем счётчик, и если перед этим счётчик был равен нулю, то присваиваем last_free текущую координату. Если текущая точка - правый конец запрещённого отрезка, то просто уменьшаем счётчик.