Покрывающий союз интервалов

Question

Я пытаюсь найти решение проблемы, которая сводится к интервалам. по поиску в Google, я знаю, что обычно это решается с помощью жадного подхода, но моей собственной первой идеей было использование поиска в ширину. Я начинаю, предполагая, что объединение интервалов является интервалом и все интервалы закрыты. Проблема:

При заданных k закрытых интервалах найти подмножество с таким количеством элементов, как возможно так, что каждая точка в интервале из исходной коллекции находится в интервале в найденном подмножестве.

Моя идея - работать в графе, где интервалы - это вершины и две вершины. сформировать ненаправленное ребро, если соответствующие интервалы перекрываются. В особом случае где объединение является интервалом, я могу выбрать узлы, содержащие конечную и начальную точку имея максимальную длину, а затем путь между ними минимальной длины является оптимальным решением. Моя проблема заключается в следующем: как эффективно построить график интервалов, чтобы избежать просмотра каждой пары интервалов. Я пробовал разные способы сортировки интервалов, но все же, похоже, не ушел от квадратичного времени.

Answer 1

Я думаю, что в худшем случае вы не сможете уйти от квадратичного времени. Это потому, что число ребер может быть квадратичным.

Но нормальный алгоритм кратчайшего пути (такой как Дейкстра) здесь не нужен. Начните с первого интервала (тот, который имеет самый низкий старт). Затем выберите интервал, который начинается после этого и чей конец самый высокий. Повторяйте, пока не дойдете до конца.

Answer 2

Я отвечаю на этот вопрос, поскольку предыдущие записи не дают правильного ответа или являются неполными, насколько мне известно.

Существует алгоритм, который работает на O (N log N), где N - этоколичество закрытых сегментов:

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

2. Примените жадную стратегию «слева направо»:

   2.1, не пропуская точку, принудительно выберите сегмент с наибольшим левым концом

   2.2 Если естьОтсутствует точка, нет решения.

   2.3 В противном случае перейдите к 2.1

Временная сложность шага 1 равна O (N log N), а временная сложность шага 2 - O (N).Следовательно, этот жадный алгоритм занимает O (N log N) времени.

Надеюсь, это поможет!