Алгоритм нахождения максимальной суммы в последовательности перекрывающихся интервалов

Question

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

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

Intervals   - Score  
   0- 5     -  15  
   4- 9     -  18  
  10-15     -  12  
   8-21     -  19  
  25-30     -  25    

Здесь интервалы 0-5, 4-9 и 8-21 перекрываются.
Также перекрываются интервалы 10-15 и 8-21.
Максимальная сумма будет 55(18 + 12 + 25).

Здесь важно отметить, что мы выбираем интервал 4-9 первой партии перекрывающихся интервалов, даже если он не имеет наибольшую оценку из трех.

Это потому, что выбор интервала 8-21 помешал бы нам использовать интервал 10-15 позже, тем самым уменьшив общую сумму (в этом случае общая сумма будет 19 + 25 = 44).

Я ищу O (nlogn) или O (n) решение этой проблемы.Я думаю, что можно использовать динамическое программирование, но я могу ошибаться.Может ли кто-нибудь предложить решение / алгоритм (ы), которые могли бы решить эту проблему?

Редактировать: интервалы не в определенном порядке.

Answer 1

Это взвешенное отклонение планирование интервалов ; это разрешимо в O(N log N) с динамическим программированием .

Пусть интервал будет g(start, stop, score), и пусть они будут отсортированы по stop. Для простоты давайте пока предположим, что все stop уникальны.

Пусть best[i] будет лучшим результатом, который мы можем получить, когда нам разрешено использовать g[1], ..., g[i]. Конечно, нам не нужно использовать их все, и, как правило, мы не можем, потому что подмножество интервалов, которые мы используем, должно быть непересекающимся.

• Понятно best[0] = 0. То есть, поскольку мы не можем использовать какой-либо интервал, лучший результат, который мы можем получить, равен 0.
• Для любого 1 <= k <= N имеем:
  • best[k] = max( best[k-1], best[j] + g[k].score ), где
    • j - это самый большой индекс, такой что g[j].stop < g[k].start (j может быть нулем)

То есть, учитывая, что нам разрешено использовать g[1], ... g[k], лучшее, что мы можем сделать, - это лучший результат этих двух вариантов:

• Мы не включаем g[k]. Таким образом, оценка этой опции составляет best[k-1].
  • ... потому что это лучшее, что мы можем сделать с g[1], ... g[k-1]
• Мы включаем g[k], и слева от нас мы делаем все возможное, чтобы все гены не перекрывались с g[k], то есть со всеми g[1], ..., g[j], где g[j].stop < g[k].start и j такие большие насколько это возможно. Таким образом, оценка этой опции составляет best[j] + g[k].score.

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

Общий ответ на вопрос: best[N], то есть лучший результат, который мы можем получить, когда нам разрешено использовать все гены. Ой, я сказал гены? Я имею в виду интервалы.

Это O(N log N), потому что:

• Сортировка всех интервалов занимает O(N log N)
• Нахождение j для каждого k равно O(log N) с использованием бинарного поиска

---

Если несколько генов могут иметь одинаковые значения stop, то ничего не изменилось: вам все равно придется искать самый правый j. Например, Python это легко с bisect_right. В Java, где стандартная библиотека двоичного поиска не гарантирует, какой индекс возвращается в случае связей, вы можете (среди многих вариантов) следовать за ним с помощью линейного поиска (для O(N) производительности в худшем случае) или другой серии двоичных файлов. выполняет поиск, чтобы найти самый правильный индекс.

Ой, я снова сказал гены? Я имею в виду интервалы.

Похожие вопросы

• Расширение бинарного поиска для поиска первого и последнего индекса значения ключа

Answer 2

Прежде всего, я думаю, что максимум 59, а не 55. Если вы выберете интервалы [0-5], [8-21] и [25,30], вы получите 15 + 19 + 25 = 59. Вы можете использовать какое-то динамическое программирование, чтобы справиться с этим.

Сначала вы сортируете все интервалы по их начальной точке, затем выполняете итерацию от конца к началу. Для каждого элемента в списке вы выбираете максимальную сумму от этой точки до последней как max(S[i]+S[j], S[i+1]), где i - элемент, на котором вы находитесь, j - элемент, который является первой неперекрывающейся записью после вашего элемента (то есть первый элемент, начало которого больше конца текущего элемента). Чтобы ускорить алгоритм, вы хотите сохранить максимальную частичную сумму S [j] для каждого элемента.

Чтобы уточнить, позвольте мне решить ваш пример в соответствии с этим. Сначала отсортируйте интервалы:

 1:  0- 5 -  15
 2:  4- 9 -  18
 3:  8-21 -  19
 4: 10-15 -  12
 5: 25-30 -  25

Итак,

 S[5] = 25
 S[4] = max(12+S[5], 25)=37
 S[3] = max(19+S[5], S[4])=max(19+25,37)=44
 S[2] = max(18+S[4], S[3])=max(18+37,44)=55
 S[1] = max(15+S[3], S[2])=max(15+44, 55)=59

Это адаптация алгоритма в этого поста , но, к сожалению, у него нет хорошего времени выполнения O (n). Вырожденный список, в котором каждая запись перекрывает следующую, может привести к значению O (n ^ 2).

Answer 3

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

S[i] обозначает оценку каждого интервала
Interval[i] обозначает все интервалы

ResMax[i] = max(ResMax[i-1] + S[i] //if i is included
           ,max(R[i-1],S[i]) 
         )

Я непроверил тщательно, но это должно работать, я верю.

Answer 4

Я немного подумал об этом и что-то придумал.

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

Построение дерева занимает O (N Log N), а поиск - O (Log N). Поскольку мы выполняем поиск всех элементов, решение становится O (N Log N).

Однако, если мы столкнемся с чем-то вроде приведенного выше примера, где самый высокий интервал оценки в одной группе уменьшает общее количество, алгоритм завершится неудачно, потому что у нас нет никакого способа узнать, что самый высокий интервал оценки не должен использоваться до этого. Очевидный способ обойти это - рассчитать оба (или все) итоговые значения в случае, если мы не уверены, но это возвращает нас к потенциально O (N ^ 2) или худшему решению.

Answer 5

Звучит как вариант проблемы с рюкзаком. Вы можете найти вдохновение в поиске этих решений.

Сколько интервалов мы говорим? Если это всего лишь около 5 (как в вашем примере), возможно, более практичным будет просто попробовать каждую комбинацию. Если это больше, подойдет ли приближение к идеальному решению? Опять же, ранцевые решения (такие как алгоритм жадного приближения Джорджа Данцига) могут быть хорошим началом.

Answer 6

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