Разработайте алгоритм, чтобы получить минимальное количество поддиапазонов, необходимое для охвата диапазона от 1 до n

Question

Может кто-нибудь помочь мне с этой проблемой с помощью некоторого псевдокода и / или объяснения того, как решить эту проблему?

Вам предоставляется список диапазонов {start, stop} и целевой длины n.Некоторые диапазоны будут перекрываться с другими диапазонами.Разработайте алгоритм, который определяет минимальное количество диапазонов, необходимое для полного охвата от 1 до n.

Например, если мне дан список диапазонов [{1,2}, {1,3}, {2,3}] и целевой длины n = 3, я должен вернуть 1, потому что нам нужно только {1,3} для покрытия от 1 до 3. Очевидно, это довольно простой тестовый пример.

Есть идеи?Я довольно озадачен.Я почти хотел разработать какой-то жадный алгоритм, но я не уверен, что это поддается жадному решению ...

Answer 1

На данный момент я думаю, что мне следует начать с сортировки списка диапазонов по их начальному элементу, но я не уверен, куда идти дальше ...

Да, это хорошее начало.

Как только вы это сделаете, вы перебираете «куски» «достижимых» диапазонов:

• Сначала вы просматриваете вседиапазоны, в которых start ≤ 1 (что означает, что они сразу "достижимы"), и найти самый большой end среди этих диапазонов - назовите его max_end ₁.
• Затем вы сканируете все диапазоны с 1 <<em> start ≤ max_end ₁ (что означает, что вы можете «достичь»"их только через один предыдущий интервал), и найдите самый большой конец среди этих диапазонов - назовите это max_end ₂ .
• Продолжайте делать это до тех пор, пока не наберете i , чтобы max_end _i ≥ n .Это i является ответом.
• Если вы когда-либо достигнете точки, где «порция» достижимых диапазонов пуста - все ваши диапазоны пока только дают вам до x (где x <<em> n ), а следующий диапазон имеет start > x , или там равно нет следующего диапазона - тогда нет ответа, потому что даже все интервалы, взятые вместе, не охватывают диапазон от 1 до n .

Обратите внимание, что, хотя выповторять только отсортированный список один раз , возможно, будет проще реализовать его, если использовать два вложенных цикла: внешний цикл для итерации по «чанкам» и внутренний цикл для итерации по интервалам в каждом"кусок".

Answer 2

Вы можете использовать Дерево интервалов .Поместите интервалы в структуру данных.

Начните с a = 1.

На каждом шаге запрашивайте дерево для интервала, который перекрывает a и имеет самый большой правый конец.Заметьте, что когда вы реализуете дерево интервалов как расширенное красно-черное дерево, вы можете сделать так, чтобы запрос дал вам оба эти условия.

Сбросить значение a в значение этого правого конца.

Повторять, пока запрос возвращает результат, и каждый раз сохранять полученный интервал в списке, который станет ответом.Остановитесь, когда a> = n.

Вернуть полученный список.

---

Доказательство того, что приведенный выше результат имеет минимальную мощность

Предположим, чтопоследовательность интервалов, упорядоченных по их левым концам, полученная выше, равна I1, I2, ..., Im, и вызовите a1, a2, ..., am, их правые концы.

Если J1, J2,..., Jr были другой последовательностью интервалов, упорядоченных по их левым концам, покрывающим [1, n] с r минимумом.Назовите b1, b2, ..., br, их права заканчиваются.

Обратите внимание, что J1 покрывает 1. Следовательно, b1 <= a1 по построению I1.Следовательно, J2 перекрывает I1.Если бы J2 были внутри I1, то последовательность J можно было бы сократить, заменив J1 и J2 на I1.Это противоречит тому, что последовательность J имеет минимальную длину.</p>

Следовательно, J2 охватывает a1.Вы можете видеть, куда это идет.Теперь повторим приведенный выше аргумент.По построению b2 <= a2.Поэтому J3 перекрывает b2.Если бы J3 были внутри I1 объединения I2, то последовательность J можно было бы сделать короче, заменив J1, J2, J3 на I1, I2, что противоречит минимальному значению r.Следовательно, J3 покрывает a3.Повторите, и в итоге вы получите это г = м. </p>