Эффективный поиск перекрывающихся интервалов из списка интервалов

Это связано с поиском перекрывающихся интервалов. Я знаю, как это сделать, учитывая список интервалов (деревья интервалов). У меня есть список интервалов. Например,

[2,6], [7,11]
[1,3], [5,10], [11,13]
[2,5], [6,8]

Результат для этого должен быть

[2,3], [7,8]

Что мне нужно сделать, так это найти список интервалов, общих для всех списков.

Я считаю эту проблему похожей на объединение n списков. Проблема в том, что я не могу применить попарное объединение списков. Применение этого метода может привести к потере перекрывающихся интервалов. Поэтому мне нужно объединить все списки вместе, рассматривая их все одновременно (а не попарно).

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

Есть ли эффективный алгоритм для поиска перекрывающихся интервалов из списка списка интервалов.?

Дополнительная информация: интервалы в списке отсортированы. Они не перекрываются и образуют последовательность.


list algorithm intervals data-structures interval-tree
person akaHuman    schedule 22.08.2013    source источник

Ответы (3)


arrow_upward
4
arrow_downward

Создайте единый отсортированный массив переходов. У каждого перехода есть позиция и совокупное число, зависящее от того, сколько интервалов вы присоединяетесь или покидаете. Проходя по списку, отслеживайте, сколько интервалов вы используете. Когда у вас столько же интервалов, сколько серий, это когда вы находитесь в общем интервале.

Для вашего примера переходы будут:

[2, 1], [6, -1], [7, 1], [11, -1],
[1, 1], [3, -1], [5, 1], [10, -1], [11, 1], [13, -1]
[2, 1], [5, -1], [6, 1], [8, -1]

который после сортировки по позиции и слияния сворачивается на:

[1, 1], [2, 2], [3, -1], [5, 0], [6, 0], [7, 1], [8, -1], [10, -1], [11, 0], [13, -1]

который дает вам переходы для промежуточных итогов:

[1, 1], [2, 3], [3, 2], [7, 3], [8, 2], [10, 2], [13, 1]

И затем мы можем считать интервалы, в которых мы находимся на 3, как один, начинающийся с 2 и идущий до 3, а другой, начинающийся с 7 и идущий до 8. Вот и ответ.

По общему признанию, идея создания одного длинного списка и сортировки - это дополнительная работа. Вместо этого вы можете создавать эти списки и объединять их на лету. Экономия - это фактор журнала количества серий, а не журнала количества событий.

person btilly    schedule 22.08.2013
comment
Извините, но я потерял вас, в котором есть переходы для промежуточных итогов. Не могли бы вы уточнить немного подробнее. Спасибо! - person akaHuman; 22.08.2013
comment
Первая запись остается позицией. Второй - это сумма изменений к этому моменту. Итак, мы начинаем [1, 1], затем [2, 1+2], затем [2, 1+2-1] и так далее (потому что изменения следуют за 1, 2, -1, 0, 0, 1, -1, -1, 0, -1). Переходы 0 не имеют значения, поэтому я их отбросил. - person btilly; 22.08.2013

arrow_upward
2
arrow_downward

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

Я бы сделал что-то вроде

Let S be the set of sets, R = s1, s1 in S
     for each set s2 in S / {s1}
              for each element e1 in R
                  for each element e2 in s2 s.t. e1.sup < e2.inf
                    e1 <- intersection (e1, e2)

И операция пересечения между двумя интервалами есть

 intersection (e1,e2):
    return new Interval(max(e1.inf, e2.inf), min (e1.sup, e2.sup));
person hpid91    schedule 22.08.2013
comment
Думаю, это решение методом грубой силы! Я с нетерпением жду более эффективного решения, если смогу его найти. - person akaHuman; 22.08.2013
comment
да, это O (n). Вы можете добиться большего в среднем случае, если ваш набор заказан (просто выйдите из второго цикла, как только вы встретите элемент e2, нижняя граница которого выше верхней границы второго элемента. Просто отредактировал псевдокод. - person hpid91; 22.08.2013

arrow_upward
2
arrow_downward

Вы сказали, что каждый отдельный список интервалов отсортирован и не перекрывается. Так,

Keep track of where you are in each list, starting at the beginning of each.
While none of the lists has run out:
    If the current intervals (one from each list) all overlap:
       Output the intersection of the current intervals
    Find which of the current intervals has the earliest end point
    Advance one position within that list.

Если существует K списков интервалов и N интервалов в целом, это должно занять время O (NK), если реализовано наиболее простым способом, но вы должны иметь возможность сократить это время до O (N log K), отслеживая информацию о текущем интервалы в куче или какой-либо другой приоритетной очереди.

person Chris Okasaki    schedule 22.08.2013