Рассмотрим вопрос, чтобы найти минимальное доминирующее множество интервального графа. В контексте интервального планирования он преобразуется в следующий вопрос:
Есть несколько интервалов, которые могут или могут перекрываться друг с другом. Найдите минимальное подмножество интервалов, чтобы для каждого интервала, не включенного в подмножество, было найдено хотя бы 1 интервал в подмножестве, который будет перекрываться с ним.
Существует согласованное жадное решение, доступное из различных источников в Интернете, например одно решение от Корнелла: http://www.cs.cornell.edu/Courses/cs4820/2011sp/handouts/samplesolutions.pdf
Мы работаем, чтобы заполнить набор C, который составляет комитет (подмножество интервалов). Мы используем набор M для удержания «покрытых» интервалов в бухгалтерском учете.
- Отсортируйте интервалы по времени окончания, начиная с самого раннего времени окончания.
- Возьмите интервал i в S с самым ранним временем финиша.
- Построить множество O = {s ∈ S | s пересекает i}
- Возьмем o ∈ O с самым поздним временем окончания и прибавим o к C, добавим все интервалы, которые пересекаются с o, к M
- повторить 2-4, пока не будут покрыты все интервалы.
Это похоже на проголосованный ответ, предоставленный interjay в 2012 году на SO: Найдите наименьший набор перекрывающихся заданий
Но я заметил контрпример, который доказывает, что приведенное выше решение не дает минимального подмножества:
Рассмотрим интервалы: [0,2], [1,4], [3,10], [5, 6], [7,8], [9, 10].
Минимальное подмножество должно иметь 2 интервала: [3, 10] плюс либо [0, 2], либо [1, 4].
Но приведенное выше решение вернет подмножество из 4 интервалов: [1,4], [5,6], [7,8] и [9,10]. Самый длинный интервал [3,10] был преждевременно отклонен на этапе 4.
Есть ли более жадное решение, чем приведенные выше? Спасибо!
