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

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

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

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) для этой проблемы. Я думаю, что можно использовать динамическое программирование, но я могу ошибаться. Может ли кто-нибудь предложить решение / алгоритм (ы), который мог бы сделать трюк здесь?

Изменить. Интервалы не имеют особого порядка.

    Это взвешенная вариация интервального планирования ; она разрешима в 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) ) или другой серии бинарный поиск, чтобы найти самый правый индекс.

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

    Связанные вопросы

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

    Прежде всего, я думаю, что максимум 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).

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

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

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

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

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

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

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

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

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

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

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

    Interesting Posts

    Почему элементы формы Bootstrap ужасно выглядят с помощью Struts2-Boostrap-Plugin?

    Как я могу освободить указатель мыши с помощью мыши в OS X?

    Как кэшировать fragmentы карты Google для автономного использования?

    Файлы настроек emacs / elisp при загрузке

    Как определить фоновую программу (в Windows 7), которая автоматически крадет активную фокус?

    Хостинг проектов ASP.NET 5 на IIS

    График Excel не отображает все серии данных

    Является ли библиотека коллекций Scala 2.8 «самой длинной записью о самоубийстве в истории»?

    Postgresql: лучше ли использовать несколько баз данных по 1 схеме или 1 базу данных с несколькими схемами?

    Преобразование Excel в формат строки

    Как анализировать дату / время из строки?

    Как создать отформатированные всплывающие подсказки в Microsoft Word

    Можно ли скрыть идентификатор SSID для Windows 7 Soft AP

    Экспорт в Excel в Asp.net MVC

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

    Давайте будем гением компьютера.