Алгоритм - группировка из перекрывающихся интервалов

Question

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

Под Группировкой я подразумеваю, что последовательные элементы группируются. И если для элемента нет последовательных элементов из других интервалов, то это рассматривается как группа с одним элементом

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

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

Пожалуйста, скажите мне, какой подход я должен принять, чтобы решить проблему.

Пример:

Интервалы (включая границы)

[1,2]
[2,4]
[3,7]
[6,11]
[9,11]
[5,11]
[10,14]
[13,14]

Возможное решение

[1,2] ==> 2
[2,4] ==> 3
[3,7] ==> 4
[6,11] ==> 10
[9,11] ==> 9
[5,11] ==> 11
[10,14] ==> 12
[13,14] ==> 13

Группы формируются путем выбора вышеуказанных элементов

2,3,4 and 9,10,11,12,13

Таким образом, есть только один разрыв от 4 до 9

Answer 1

Эта проблема была впервые решена в:

П. Батист. Блок планирования задач для минимизации количества периодов простоя: алгоритм полиномиального времени для автономного динамического управления питанием. В материалах 17-го ежегодного симпозиума ACM-SIAM по дискретному алгоритму, стр. 364–367, Майами, Флорида, 2006.

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

Однако есть и эта статья:

Планирование, чтобы минимизировать разрывы и энергопотребление

Эрик Д. Демейн, Мохаммад Годси, Мохаммад Таги Гаджиагайи Амин С. Сайеди-Рошхар, Мортеза Задимогаддам

которая расширяет задачу для планирования задач на нескольких процессорах и дает решение O(n^7p^5), где n - число интервалов, а p - число процессоров.

В вашем случае p=1, так что это дает решение O(n^7).

Если это слишком медленно, то вы также можете попробовать приблизительное решение, описанное в статье, которое пытается сделать каждый пробел как можно большим.