Я пытался найти эффективный способ решить эту проблему - найти «минимальные» (не минимальные) временные точки, но не уверен, что это так просто.Я попытался смоделировать ее как задачу минимального покрытия ребер (сложность полиномиального времени «P»: интервалы - это вершины, а пересечение интервалов - это ребро), но это не сработало, потому что в одном временном пункте в оптимальном решении может быть несколько ребер.
Я разработал жадное решение: сортируйте интервалы в порядке возрастания их конечного времени.Затем выполните итерации по интервалам в порядке.Если момент времени не был вставлен в решение, охватывающее текущий интервал, вставьте его и удалите все рассматриваемые интервалы из рассмотрения.Продолжайте, пока не останется никаких интервалов.Пример: (0, 10), (3, 12), (11, 15)
Добавьте время 10 к раствору.Снять (0, 10) и (3, 12) с рассмотрения.Добавьте время 15 к решению.Снять (11, 15) с рассмотрения.Окончательное решение имеет размер 2. (время 10 и 15).
Я не могу доказать, что это оптимально, потому что он не смоделирован как покрытие края или покрытие вершины или известная проблема графа.Я пытался смоделировать его как «проблему минимального прикрытия клика», но не уверен, что оно работает.
- Как правильно смоделировать его, чтобы понять его сложность (сложность P против NP)?
- Какузнать, является ли вышеуказанное решение оптимальным?