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

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

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

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

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

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ

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

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

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

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

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

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

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

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

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

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

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

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

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

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