Найдите наименьший набор перекрывающихся заданий

Question

Друг дал мне загадку, которую, по его словам, можно решить быстрее, чем за O (n ^ 3).

При заданном наборе из n заданий, каждое из которых имеет заданное время начала и время окончания (перекрытияочень возможно), найдите наименьшее подмножество, которое для каждой работы либо включает эту работу, либо включает работу, которая частично совпадает с этой работой.

Я почти уверен, что оптимальным решением будет выбрать работу с помощьюбольшинство немаркированных перекрытий, добавьте его в набор решений, затем отметьте его и его перекрытие.И повторять до тех пор, пока все задания не будут помечены.
Определение того, какое задание имеет наиболее немаркированные перекрытия, представляет собой простую матрицу смежности (O (n ^ 2)), и ее необходимо повторять каждый раз при выборе задания, чтобыобновить отметки, сделав его O (n ^ 3).

Есть ли лучшее решение?

Answer 1

Пусть A будет набором заданий, которые мы еще не перекрыли.

1. Найдите задание x в A, которое имеет минимальное время окончания (t).
2. Из всех заданий, время начала которых меньше t: выберите задание j с максимальным временем окончания.
3. Добавьте j к выходному набору.
4. Удалите все задания, которые перекрываются j с A.
5. Повторяйте 1-4, пока A не станет пустым.

Простая реализация будет выполняться в O (п ^ 2).Используя деревья интервалов , вероятно, можно решить в O (n * logn).

Основная идея, почему это оптимальное решение (не формальное доказательство): Мы должны выбрать одну работувремя начала которого меньше t, так что x будет перекрываться.Если мы позволим S быть набором всех заданий, время начала которых меньше t, можно показать, что j будет перекрывать те же задания, что и любое задание в S, плюс, возможно, больше.Поскольку нам нужно выбрать одну работу в S, лучший выбор - j.Мы можем использовать эту идею, чтобы сформировать доказательство по количеству рабочих мест.

Answer 2

Мы можем достичь решения O (nlogn) с помощью подхода динамического программирования. В частности, мы хотим рассмотреть размер наименьшего набора, включая задание k ^th и сопоставление первых k заданий (упорядоченных по времени начала), которые мы обозначим S(k). Сначала мы должны добавить вспомогательное задание (∞, ∞), поэтому результатом будет наше решение DP для этого окончательного задания минус один.

Чтобы вычислить S(k), рассмотрим задание p(k), которое заканчивается до задания k, но имеет максимальное время начала. Обратите внимание, что p является возрастающей функцией. S(k) будет тогда на единицу больше минимального S(i) с end(i) > start(p(k)).

Мы можем эффективно найти эту работу, поддерживая (S(k) упорядоченный минимум) кучу потенциальных работ. После вычисления каждого S(k) мы добавляем задание в кучу. Когда мы хотим получить работу, мы удаляем рабочие места в куче, которые заканчиваются слишком рано, пока не найдем подходящую. В общей сложности это займет не более O (nlogn), поскольку мы выполняем не более O (n) каждой операции кучи (pop / peek / push).

Остальная часть задачи заключается в эффективном вычислении значений p(k). Один из способов сделать это - перебирать все начало и конец задания (с увеличением времени), отслеживая последнее начальное задание.