поиск интервального перекрытия в списке интервалов?

Question

Скажем, [a, b] представляет интервал на реальной линии от a до b, a < b включительно (т.е. [a, b] = множество всех x таких, что a < = x < = b). Кроме того, скажем, [a, b] и [c, d] являются «перекрывающимися», если они разделяют любое x, так что x находится в обоих [a, b] и [c, d].

Учитывая список интервалов ([x1, y1], [x2, y2], ...), что является наиболее эффективным способом нахождения всех таких интервалов, которые перекрываются с [x, y]?

Очевидно, что я могу попробовать каждый и получить его в O (n). Но мне было интересно, могу ли я сортировать список интервалов каким-то умным способом, я мог бы найти/один/перекрывающий элемент в O (log N) через двоичный поиск, а затем «оглянуться» с этой позиции в списке, чтобы найти все перекрывающиеся интервалы. Однако как мне сортировать интервалы, чтобы такая стратегия работала?

Обратите внимание, что в элементах списка могут быть перекрытия между элементами, что и делает это трудным.

Я пробовал, сортируя интервалы по их левому краю, справа, по середине, но ни один из них не ведет к исчерпывающему поиску.

Помощь?

Answer 1

[a, b] перекрывается с [x, y], если b> x и a < y. Сортировка интервалов по их первым элементам дает вам интервалы, соответствующие первому условию во время журнала. Сортировка интервалов по их последним элементам дает вам интервалы, соответствующие второму условию во время журнала. Возьмите пересечения результирующих множеств.

Answer 2

Просто так быстро подумайте «с манжетой», так сказать.

Не могли бы вы организовать их в 2 списка, один для начала интервалов, а другой для конца интервалов.

Таким образом, вы можете сравнить y с элементами в начале списка интервалов (скажем, бинарным поиском), чтобы сократить кандидатов на основе этого.

Затем вы можете сравнить x с элементами в конце списка интервалов.

EDIT

Корпус: После выключения

Если вы сравниваете только одного интервала в список интервалов в однократном от ситуации, я не верю, что сортировка поможет вам since ideal sorting is O(n).

Выполняя линейный поиск по всем x, чтобы обрезать любые невозможные интервалы, затем, выполняя другой линейный поиск по оставшимся y, вы можете уменьшить свою общую работу. В то время как это все еще O (n), без этого вы бы делали 2n сравнения, тогда как в среднем вы делали бы (3n-1)/2 сравнения таким образом.

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

Корпус: предварительная сортировка не считается

В том случае, если вы будете постоянно сравнивая единичные интервалы в этот список интервалов и вашей предварительной сортировки в списке, вы можете достичь лучших результатов. Этот процесс все еще применяется, но, выполняя двоичный поиск в первом списке, а затем вы можете получить O (m log n) в отличие от O (mn), где m - количество сравниваемых единичных интервалов. Обратите внимание, что все еще дает вам преимущество сокращения общих сравнений. [2m log n по сравнению с m (3 (log n) - 1)/2]

Answer 3

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

Например, если интервалы

[1,4], [3,6], [4,5], [2,8], [5,7], [1,2], [2,2.5] 

и вы найти совпадение с [3,4] затем сортировать по левому краю и отмечая положение правого конца теста (с правой стороны, как раз больше, чем его значение, так что 4 входит в диапазон)

[1,4], [1,2], [2,2.5], [2,8], [3,6], [4,5], *, [5,7] 

[5,7] вы знаете, не могут перекрываться, то сортировка по правой части и маркировки позиции левого конца теста

[1,2], [2,2.5], *, [1,4], [4,5], [3,6], [5,7], [2,8] 

вы знаете [1,2] и [2,2.5] не могут перекрываться

Не уверен, насколько эффективно это будет так как вы того, чтобы сделать два вида и поисковые запросы.

Answer 4

A 'quadtree' - это структура данных, которая часто используется для повышения эффективности обнаружения столкновений в двух измерениях.

Я думаю, вы могли бы создать аналогичную 1-ю структуру. Это потребует некоторых предварительных вычислений, но должно привести к производительности O (log N).

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

Затем, проверяя интервал, вы в основном находите все листовые узлы, в которые он будет вставлен, были ли вставлены, проверьте частичные интервалы внутри этих узлов для пересечения, а затем сообщите об этом интервале, который был записан против них, как «оригинал 'родитель.

Answer 5

Как вы можете видеть в других ответах, большинство алгоритмов объединяются со специальной структурой данных. Например, для несортированного списка интервалов в качестве ввода O(n) лучше всего вы получите. (И, как правило, легче думать с точки зрения структуры данных, которая диктует алгоритм).

В этом случае, ваш вопрос не является полным:

• Вы дали целый список или это вы на самом деле создает?

• Вам нужно выполнить только один такой поиск или многие из них?

• Есть ли у вас какие-либо оценки для операций, которые он должен поддерживать и их частоты?

Например, если вам нужно выполнить только один такой поиск, тогда не стоит сортировать список раньше. Если многие, то более дорогая сортировка или генерация «1D quadtree» будет амортизирована.

Однако, это было бы трудно решить, потому что простая квадтрия (как я ее понимаю) способна только обнаружить коллизию, но она не в состоянии создать список всех сегментов, которые перекрываются с вашим вводом ,

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

Answer 6

Для полноты я хотел бы добавить, что существует известная структура данных для такого рода проблем, известных (сюрприз, сюрприз) как interval tree. Это в основном расширенное сбалансированное дерево (красный-черный, AVL, ваш выбор), в котором хранятся интервалы, отсортированные по их левой (нижней) конечной точке. Увеличение состоит в том, что каждый узел хранит наибольшую правую (высокую) конечную точку в своем поддереве. Это дерево позволяет найти все перекрывающиеся интервалы времени O (log n).

Это описано в CLRS 14.3.