Максимальные неперекрывающиеся интервалы в дереве интервалов

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

Например,

если у нас есть следующие интервалы:

[0600, 0830], [0800, 0900], [0900, 1100], [0900, 1130], 
[1030, 1400], [1230, 1400]

Также указывается, что время должно быть в диапазоне [0000, 2400].

Максимальное непересекающееся множество интервалов [0600, 0830], [0900, 1130], [1230, 1400].

Я понимаю, что максимальная упаковка упаковки NP-Complete. Я хочу подтвердить, что моя проблема (с интервалами, содержащими только начальное и конечное время) также является NP-Complete.

И если да, то есть ли способ найти оптимальное решение в экспоненциальном времени, но с более разумной предварительной обработкой и обрезкой данных. Или, если относительно легко реализовать алгоритм с фиксированным параметром. Я не хочу использовать алгоритм аппроксимации.

Ответ 1

Это не проблема NP-Complete. Я могу придумать алгоритм O(n * log(n)), используя динамическое программирование для решения этой проблемы.

Предположим, что n интервалов. Предположим, что данный интервал S (в вашем случае S = [0000, 2400]). Либо предположите, что все интервалы находятся в пределах S, либо исключают все интервалы, не входящие в S в линейном времени.

Pre-процесса:
- Сортировка всех интервалов по их начальным точкам. Предположим, мы получаем массив A[n] из n интервалов.
  - Этот шаг занимает O(n * log(n)) время
- Для всех конечных точек интервалов найдите индекс наименьшей начальной точки, которая следует за ней. Предположим, мы получаем массив Next[n] из n целых чисел.
  - Если такая точка начала не существует для конечной точки интервала i,, мы можем назначить n на Next[i].
  - Мы можем сделать это в O(n * log(n)) раз, перечислив n конечных точек всех интервалов и используя двоичный поиск, чтобы найти ответ. Возможно, существует линейный подход к решению этого вопроса, но это не имеет значения, потому что предыдущий шаг уже занимает время O(n * log(n)).
DP:
- Предположим, что максимальные неперекрывающиеся интервалы в диапазоне [A[i].begin, S.end] равны f[i]. Тогда f[0] - ответ, который мы хотим.
- Также предположим f[n] = 0;
- Уравнение перехода состояния:
  - f[i] = max{f[i+1], 1 + f[Next[i]]}
- Совершенно очевидно, что шаг DP принимает линейное время.

Вышеупомянутое решение - это тот, который я придумал с первого взгляда на проблему. После этого я также придумываю жадный подход, который проще (но не быстрее в смысле большой записи O):

(с теми же обозначениями и предположениями, что и подход DP выше)

Предварительная обработка. Сортируйте все интервалы по их концу. Предположим, мы получаем массив B[n] из n интервалов.

Жадный:

int ans = 0, cursor = S.begin;
for(int i = 0; i < n; i++){
    if(B[i].begin >= cursor){
        ans++;
        cursor = B[i].end;
    }
}

Вышеупомянутые два решения вытекают из моего разума, но ваша проблема также упоминается как проблема выбора активности, которую можно найти в Википедии http://en.wikipedia.org/wiki/Activity_selection_problem.

Кроме того, введение в алгоритмы подробно обсуждает эту проблему в 16.1.