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

Скажем, [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) через двоичный поиск, а затем "оглянуться" с этой позиции в списке, чтобы найти все перекрывающиеся интервалы. Однако как мне сортировать интервалы, чтобы такая стратегия работала?

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

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

Справка

Ответ 1

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

Ответ 2

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

Он описан в CLRS 14.3.

Ответ 3

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

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

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

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

Ответ 4

Просто быстрая мысль "с манжетой", так сказать.

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

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

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

ИЗМЕНИТЬ

Случай: после выключения

Если вы сравниваете только один интервал с перечнем интервалов в разовой ситуации, я не считаю, что сортировка поможет вам поскольку идеальная сортировка это O (n).

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

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

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

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

Ответ 5

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

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

[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] не могут пересекаться

Не уверен, насколько это будет эффективно, так как вам нужно делать два вида и поиска.

Ответ 6

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

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

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

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

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

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

Ответ 7

Программа С++ объединяет перекрывающиеся интервалы
Использует сортировку слияния
Примеры инверсий: (8, 9); (3, 4); (2, 5); (1, 2); (6, 7)
Ответ: (1, 5); (6, 7); (8, 9)
Требование: начало < конец, то есть (6, 5), не является допустимым интервалом

См. Код