#algorithm
#алгоритм
Вопрос:
Я ищу алгоритм, который поможет мне в реализации проблемы! Проблема заключается в следующем:
Существует список диапазонов, мне нужно создать список с подмножеством неперекрывающихся диапазонов (не обязательно смежных), чтобы сумма их длин была максимально возможной.
Например, для входного списка
[(-1, 3), (2, 4), (0, 5), (-4, -1)]
желаемый результат
[(0, 5), (-4, -1)]
с суммой длин (5 — 0) ((-1) — (-4)) = 5 3 = 8
Комментарии:
1. Что такое «максимальное значение»? Какое значение вы хотите максимизировать?
2. Какая сумма? Какова «сумма» в примере [(1,2), (4,6)]: это 3 = [2-1] [6-4] или 5 = [6-1] …?
3. короче говоря, общая длина диапазонов.
4. @Treycos В данном случае это было довольно неоднозначно, потому что интервалы имеют общий конец, поэтому сумма длин интервалов равна их общему промежутку. Вот почему я спросил о другом примере с отверстием.
5. @deniska369 Хорошо, так что, если вы имели в виду [(1,2), (4,6)] -> [2-1] [6-4] = 3, тогда почему ваш пример является результатом [(-1, 3), (-4, -1)] с суммой 7, вместо [(0,5), (-4, -1)] с суммой 8 …?!
Ответ №1:
Это задача с максимальным взвешенным независимым набором, где веса равны длине интервалов.
Это можно решить с помощью динамического программирования. Пусть интервалы будут отсортированы по времени начала.
Затем определите DP[I_j] = максимально взвешенный набор интервалов, такой, который I_j выбран, и рассматриваются только интервалы, предшествующие I_j . Это означает, что интервалы, пересекающиеся с I_j , не должны учитываться.
DP[I_j] = MAX(DP[I_r]) Wt(I_j)
Где I_r находятся интервалы, которые встречаются раньше I_j .
Временная сложность — это O(n^2) где n — количество интервалов.