Пропустить слот, который уже забронирован, и перепланировать слоты [дублировать]

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

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

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

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

EDIT

Случай: Once Off

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

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

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

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

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

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

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