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