Допустим, у нас есть множество интервалов [s1,e1],[s2,e2]...[sn,en]алгоритм выбора интервала
Я хотел бы найти подмножество непересекающихся интервалов и имеет максимальное суммарное время.
На самом деле я ищу жадное решение. Существует ли это или нет?
«Жадный» не является официальным термином, но для целей данного вопроса, давайте определим класс жадных алгоритмов, те, которые налагают априори общего порядка на интервалах (т.е. не зависит от входа) и многократно расширять частичное решение на максимально доступный интервал. Рассмотрим входы
[0,2],[1,4],[3,5]
[0,2],[1,4]
[1,4],[3,5].
Существует три возможности для максимального интервала между [0,2], [1,4], [3,5]. Если [0,2] или [3,5] максимальны, то жадный алгоритм неправильно отвечает за второй или третий вход соответственно. Если [1,4] максимально, то жадный алгоритм неправильно отвечает за первый вход.
В этих трех входах будет использоваться жадный подход O (N^2). например, для первого случая мы начнем принимать первый интервал [0,2], а затем проигнорируем 2-й (потому что он пересекается с [0,2]) и занимает третье. на следующем шаге мы возьмем второй и сравним, и мы получим, что интервал [0,2] + [3,5] является лучшим Для второго ввода мы начнем с [0,2 ]. Он пересекается с [1,4]. Итак, снова мы начинаем с [1,4]. И мы находим, что лучше всего [1,4]. То же самое для третьего входа. но на этот раз мы обнаружим, что первое лучше. Для этой проблемы нет ** жадного решения, но эти случаи кажутся слабыми. – Fallen
@MuhammedHedayet Это не «жадный» алгоритм. Я понятия не имею, что для вас жадное средство, и поэтому вы не знаете, почему вы так уверены, что не существует жадного алгоритма. –
почему это не жадный? :) Я начинаю с любого интервала и выбираю следующий интервал жадно, чтобы следующий интервал не пересекался с предыдущим. ** Жадный алгоритм всегда делает выбор, который лучше всего выглядит на данный момент ** Я надеюсь, что это ответ, почему нет жадного алгоритма для этой конкретной проблемы :) – Fallen
Это не слишком сложно, используя динамическое программирование. Подсказка: сколько вы можете заполнить до каждого 'en'? –
Это очень распространенная проблема. Вы уверены, что попробовали достаточно? – Fallen
Возможный дубликат [Алгоритм для нахождения максимальной суммы в последовательности перекрывающихся интервалов] (http://stackoverflow.com/questions/3243234/algorithm-to-find-the-maximum-sum-in-a-sequence-of -пересекающиеся интервалы) –