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

Question

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

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

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

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

Справка?

Answer 1

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

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

Answer 2

[a, b] перекрывается с [x, y] тогда и только тогда, когда b> x и a

Answer 3

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

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

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

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

Answer 4

Просто быстрая мысль, так сказать, «из-под ног».

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

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

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

EDIT

Случай: однажды выключен

Если вы сравниваете только один интервал со списком интервалов в разовой ситуации, я не верю, что сортировка поможет вам , поскольку идеальная сортировка 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 5

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

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

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

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

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

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

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

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

Answer 6

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

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

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

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