Sub O (n ^ 2) алгоритм подсчета вложенных интервалов?

У нас есть список интервалов вида [a_i, b_i]. Для каждого интервала мы хотим подсчитать количество других вложенных в него интервалов.

Например, если у нас было два интервала, A = [1,4] и B = [2,3]. Тогда счетчик для B будет 0, поскольку для B нет вложенных интервалов; и счетчик для A будет 1, поскольку B помещается внутри A.

Мой вопрос в том, существует ли алгоритм sub O(n²) для этой проблемы, где n - количество интервалов?

EDIT: Ниже приведены условия, с которыми встречаются интервалы. Конечные точки интервалов представляют собой числа с плавающей запятой. Нижний предел для a _i 's/b _i равен 0, а верхний предел - любое максимальное значение float. Кроме того, существует условие, что _i < b _i, поэтому интервалы длины 0.

Ответ 1

Да, это возможно.

Мы возьмем типичный трюк "scan line" вычислительной геометрии.

Во-первых, позвольте ответить на более простой (но тесно связанный) вопрос. Вместо того, чтобы сообщать, сколько еще интервалов содержит каждый интервал, сообщите, сколько интервалов содержится в каждом. Таким образом, для вашего примера с двумя интервалами интервал I0 = [1,4] имеет значение 0, потому что он содержится в нулевых интервалах, тогда как I1 = [2,3] имеет значение одно, потому что оно содержится в одном интервале.

Вы увидите через минуту (а), почему этот вопрос будет проще, и (б) как это приведет к ответу на исходный вопрос.

Чтобы решить этот более простой вопрос: возьмите все начальные и конечные точки - все _i и b _i - и поместите их в главный список. Вызовите каждый элемент этого списка "событие". Таким образом, событие будет выглядеть как "интервал я ₃₇ запущен" или "интервал я ₂₃ закончился".

Сортировка этого списка событий и его обработка в порядке.

Когда вы обрабатываете список событий, поддерживайте набор S "активных интервалов". Интервал является "активным", если мы встретили его событие начала, но не его конечное событие; то есть, если мы находимся в пределах этого интервала.

Теперь, когда мы видим конечное событие b _j, мы готовы вычислить, сколько интервалов содержит я _j (= [a _j, b _j]). Все, что нам нужно сделать, это проверить множество S активных интервалов и определить, сколько из них было начато до _j. Это наш ответ на то, сколько интервалов содержит интервал я _j.

Чтобы сделать это эффективно, сохраните S, отсортированную по начальной точке; например, используя самобалансирующееся двоичное дерево.

Сортировка списка событий - O (2n log 2n) = O (n log n). Добавление или удаление элемента из самобалансирующегося двоичного дерева - O (log n). Задавая вопрос: "Сколько элементов самобалансирующегося двоичного дерева меньше x?" также O (log n). Поэтому весь этот алгоритм O (n log n).

Итак, это решает простой вопрос. Назовите этот "простой алгоритм" . Теперь за то, что вы действительно просили.

Подумайте о том, как числовая линия расширяется до бесконечности и обертывается вокруг -infinity и определяет интервал с b _i < a _i, чтобы начать с _i, растянуть на бесконечность, обернуть на минус бесконечность и закончить с помощью b _i.

Для любого интервала я _j= [a _j, b _j] определите Дополнение (I _j) в качестве интервала [b _j, a _j]. (Например, интервал [2, 3] начинается с 2 и заканчивается на 3, поэтому Дополнение ([2,3]) = [3,2] начинается с 3, растягивается до бесконечности, обертывается до -инфекции и заканчивается на 2.)

Обратите внимание, что интервал я содержит интервал J тогда и только тогда, когда Complement (J) содержит Дополнение (I). (Докажите это.)

Итак, мы можем ответить на ваш первоначальный вопрос, просто выполнив "простой алгоритм" на множестве дополнений всех интервалов. То есть, начните сканирование с -infinity с помощью набора S "активных интервалов", содержащих все интервалы (поскольку все дополнения содержат бесконечность/-инфекцию). Держите S отсортированным по конечной точке (то есть начальной точке дополнения).

Отсортируйте все начальные точки и конечные точки и обработайте их по порядку. Когда вы сталкиваетесь с начальной точкой для интервала я _j (= [a _j, b _j]), вы фактически нажимаете конечную точку его дополнение... Так что удалим я _j из S, запросите S, чтобы увидеть, сколько его конечных точек (то есть точек начала дополнения) выходят до b _j и сообщают, что as ответ для я _j. Если вы позже встретите конечную точку я _j, вы столкнулись с начальной точкой своего дополнения, поэтому вам нужно добавить ее обратно в набор S активных интервалов.

Этот окончательный алгоритм является O (n log n) по тем же причинам, что и "простой алгоритм" .

[Обновление]

Одно пояснение, одна коррекция, один комментарий...

Разъяснение: Конечно, "самобалансирующееся двоичное дерево" должно быть дополнено так, что каждое поддерево знает, сколько элементов оно содержит. В противном случае вы не можете ответить "сколько элементов меньше x?" Это увеличение простое для поддержания, но это не то, что обеспечивает каждая реализация; например С++ std::set, насколько мне известно, не знает.

Коррекция: вы не хотите добавлять какие-либо элементы в набор S активных интервалов; на самом деле это может привести к неправильному ответу. Например, если интервалы равны только [1,2] и [3,4], вы ударите 1 (и удалите [1,2] из набора), затем 2 (и снова добавьте его), затем 3... И так как 2 4, вы должны сделать вывод, что [3,4] содержит [1,2]. Это неправильно.

Понятно, что вы уже обработали все "начальные события" для интервалов комплемента; поэтому S начинается все интервалы внутри него. Итак, все, о чем вам нужно беспокоиться, это конечные точки; вы не хотите добавлять какие-либо элементы в S, когда-либо.

Другими словами, вместо того, чтобы обтекать интервалы, вы можете думать о [b _i, a _i] (где b _i > a _i) как значение [b _i - бесконечность, _i] без обтекания. Логика все еще работает, но обработка более понятна: сначала вы обрабатываете все термины "независимо от бесконечности" (т.е. Конечные точки), а затем обрабатываете другие (то есть начальные точки).

С этой коррекцией я уверен, что мое решение действительно работает. Эта формулировка также распространяется, я думаю, на случай, когда у вас есть как нормальные, так и "обратные" интервалы вместе на одном входе.

Комментарий: эта проблема сложна, потому что, если вам нужно перечислить множество интервалов, содержащихся в каждом интервале, сам вывод может быть O (n ^ 2). Поэтому любой рабочий подход должен каким-то образом считать интервалы, даже не имея возможности идентифицировать их: -).

Ответ 2

Вот O (N * LOG (N)):

пусть Ii = интервал я = (ai, bi)

пусть L = список интервалов I

сортировать L по ai

разделите L пополам на L1a и L2a.

сортировать L1a и L2a на bi, чтобы получить L1b и L2b

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

Теперь вы обновили подсчет того, как часто интервал в L2 вложен внутри интервала в L1.

после слияния L1 и L2, повторим процесс (рекурсию), разделив L1 на L11a и l12a, также разделив L2 на L21a и L21a..