Поиск самой длинной пары перекрывающихся интервалов

Вот подход, который занимает N log(N) времени.

Разбейте каждый интервал [a,b] [c,d] на массив пар следующим образом:

pair<a,-1>
pair<b,a>
pair<c,-1>
pair<d,c>

sort these pairs in increasing order. Since interval starts are marked as -1, in case of ties interval they should come ahead of interval ends.

for i = 0 to end of the pair array
    if current pair represents interval start
        put it in a multiset
    else
        remove the interval start corresponding to this interval end from the multiset.
        if the multiset is not empty
            update the maxOverlap with (current_interval_end - max(minimum_value_in_multiset,start_value_of_current_interval)+1)

Этот подход должен обновить maxOverlap до максимально возможного значения.

Сохраняйте информацию о двух самых больших перекрывающихся интервалах max1 и max2 (вначале пустых).

Отсортируйте входной список [x1, y1] .. [xn, yn] = I1..In по значению x, отбрасывая более короткий из двух интервалов, если встречается равенство. Выбрасывая интервалы, обновляйте max1 и max2.

Для каждого интервала добавьте атрибут max в линейном времени, показывающий наибольшее значение y из всех предыдущих интервалов (в отсортированном списке):

rollmax = −∞
for j = 1..n do
  Ij.max = rollmax
  rollmax = max(rollmax, Ij.y)

В отсортированном, отфильтрованном и расширенном списке ввода выполните следующий запрос. Он использует постоянно расширяющийся подсписок интервалов, меньших, чем искомый в настоящее время интервал Ii, в качестве входных данных для рекурсивной функции SearchOverlap.

for i = 2..n do
  SearchOverlap(Ii, 1, i − 1)
return {max1, max2}

Функция SearchOverlap использует подход divide and conquer для обхода отсортированного списка Il, .. Ir. Он представляет такой список как полное бинарное дерево с интервалом Ic в качестве его локального корня. Тест Ic.max < I.max используется, чтобы всегда принимать решение об обходе бинарного дерева (идти влево/вправо) в направлении интервала с наибольшим перекрытием с I. Обратите внимание, что I — это запрошенный интервал, который сравнивается с log(n) другими интервалами. Также обратите внимание, что при таком обходе может быть пройден максимально возможный интервал перекрытия, отсюда и проверка на наибольшее перекрытие в начале функции SearchOverlap.

SearchOverlap(I , l, r)
c = ceil(Avg(l, r)) // Central element of queried list
if Overlap(max1, max2) < Overlap(I , Ic) then
  max1 = I
  max2 = Ic
if l ≥ r then
  return
if Ic.max < I.max then
  SearchOverlap(I , c + 1, r)
else
  SearchOverlap(I , l, c − 1)
return

Наибольшие перекрывающиеся интервалы (если они не пустые) возвращаются в конце. Общая сложность O(n log(n)).