Поиск "максимальный" перекрытия интервала пары в O (NLog (п))

Question

Постановка задачи

вход набор п интервалов; {[s_1, t_1], [s_2, t_2], ..., [s_n, t_n]}.

Выход пара интервалов; {[s_i, t_i], [s_j, t_j]}, с максимумом перекрываются между всеми парами интервалов.

Пример

входные интервалы: {[1, 10], [2, 6], [3,15], [5, 9]}

-> Есть возможно 6 интервал пар. Среди этих пар, [1,10] & [3,15] имеет наибольшее возможное перекрытие 7.

выход: {[1,10], [3,15]}

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

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

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

Любые предложения помогут!

Answer 1

Сначала отсортируйте интервалы: сначала левой конечной точкой в ​​порядке возрастания, затем — в качестве вторичного критерия — по правой конечной точке в порядке убывания. Для остальной части этого ответа я буду считать, что интервалы уже отсортированы по порядку.

Теперь есть две возможностей для того, что может быть максимально возможное перекрытие:

• может быть между интервалом и последующим интервалом, что она полностью покрывает.
• это может быть между интервалом и самым следующим интервалом, который он не полностью покрывает.

Мы можем охватить оба случай в O (п) время перебора интервалов, отслеживание следующего:

• самого большое перекрытие мы видели до сих пор, и соответствующее пара интервалов.
• последний интервал, который мы видели, назовите его L, который не был полностью покрыт ни одним из его предшественников.(Для этого ключевое понимание заключается в том, что благодаря упорядочению интервалов мы можем легко сказать, полностью ли покрыт интервал любым из его предшественников —, и поэтому, если нам нужно обновить L , просто проверив, полностью ли это покрыты текущей L. Таким образом, мы можем держать L последнюю дату в O (1) времени.)

и вычисление каждого интервала перекрытия с L.

Итак:

result := [] 
max_overlap := 0 
L := sorted_intervals[1] 
for interval I in sorted_intervals[2..n]: 
    if L.right - I.left >= max_overlap: 
     result := [L, I] 
     max_overlap := L.right - I.left 
    if I.right > L.right: 
     L := I 

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