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

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

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

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

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

Ответ 1

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

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

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

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

Ответ 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). Один из способов сделать это - перебрать все начальные и конечные задания (в увеличении времени), отслеживая последнее стартовое задание.