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

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

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

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

РЕДАКТИРОВАТЬ: Вот условия, которые соответствуют интервалам. Конечные точки интервалов являются числами с плавающей точкой. Нижний предел дляi«S / Bi's равно 0, а верхний предел равен максимальному числу с плавающей точкой. Кроме того, существует условие, чтоi <бi, поэтому нет интервалов длины 0.

 mandy18 окт. 2012 г., 05:28
Я только что прочитал о них в Википедии, но я не уверен, как их использовать. Можете ли вы сказать мне, что вы думали?
 StarPinkER18 окт. 2012 г., 05:17
Может ли интервальное дерево или сегментное дерево сделать это?
 higuaro18 окт. 2012 г., 06:23
Какой у вас интервал значений? Я имею в виду, какие значения a_i, b_i могут принимать?
 mandy18 окт. 2012 г., 06:27
Они могут быть числами с плавающей запятой. Нижний предел равен 0, а верхний предел равен максимальному значению с плавающей точкой. Также есть условие, что a_i> b_i, поэтому интервалы длины 0 отсутствуют.
 StarPinkER18 окт. 2012 г., 06:05
Это хорошо для обнаружения перекрытия, но для вложения, возможно, потребуется пересмотреть.

Ответы на вопрос(2)

Решение Вопроса

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

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

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

Чтобы решить этот более простой вопрос: взять все, начинаяи окончание очки - всеi и бi - и поместите их в основной список. Назовите каждый элемент этого списка "событием". Таким образом, событие будет что-то вроде «интервал I37 начал "или" интервал I23 закончилась».

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

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

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

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

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

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

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

Для любого интервала яj = [аj, бj], определить дополнение (Ij) как интервал [бj,j]. (Например, интервал [2, 3] начинается в 2 и заканчивается в 3; поэтому Complement ([2,3]) = [3,2] начинается в 3, простирается до бесконечности, переносится в -infinity и заканчивается в 2.)

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

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

Сортируйте все начальные и конечные точки и обработайте их по порядку. Когда вы сталкиваетесь с отправной точкой для интервала Ij (= [аj, бj]), вы на самом деле поражаете конечную точку своего дополнения ...j из S запросите S, чтобы увидеть, сколько его конечных точек (т. е. c, начальных точек дополнения) предшествуют bjи сообщить, что в качестве ответа для Ij, Если вы позже столкнетесь с конечной точкой Ijвы сталкиваетесь с начальной точкой его дополнения, поэтому вам нужно добавить его обратно в набор S активных интервалов.

Этот последний алгоритм равен O (n log n) по тем же причинам, что и «простой алгоритм».

[Обновить]

Одно уточнение, одно исправление, один комментарий ...

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

Исправление: Вы делаетене хотите добавить любые элементы обратно в набор S активных интервалов; на самом деле, это может привести к неправильному ответу. Например, если интервалы равны [1,2] и [3,4], вы нажмете 1 (и удалите [1,2] из набора), затем 2 (и добавите его снова), затем 3 ... А так как 2 <4, вы пришли бы к выводу, что [3,4] содержит [1,2]. Что не так.

Концептуально вы уже обработали все «стартовые события» для интервалов дополнения; именно поэтому S начинает все интервалы внутри него. Так что все, что вам нужно беспокоиться, это конечные точки; вы делаетене хочу добавить любые элементы в S, когда-либо.

Другими словами, вместо того, чтобы обернуть интервалы, вы можете думать о [bi,i] (где бi > аi) как значение [бi - бесконечностьi] без обхода. Логика все еще работает, но обработка более ясна: сначала вы обрабатываете все термины «что угодно - бесконечность» (то есть конечные точки), затем вы обрабатываете другие (то есть начальные точки).

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

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

 Nemo18 окт. 2012 г., 16:44
@Mandy: Да, это тоже работает :-)
 user176848023 окт. 2012 г., 15:29
@mandy: Ваше простое решение не работает в O (nlogn), потому что подумайте о наихудшем случае, и вставка в конце списка для каждого интервала подразумевает, что ваш алгоритм O (n²) в худшем случае.
 mandy18 окт. 2012 г., 12:47
Пока я разрабатывал детали вашего алгоритма, меня осенило гораздо более простое решение, которое было несколько вдохновлено тем, что вы сказали. Сначала возьмите список интервалов и отсортируйте их в порядке возрастания на основе их конечных точек. Затем выполните итерации по интервалам по порядку и добавьте их один за другим в отсортированный список, который должен быть отсортирован в начальной конечной точке. Когда интервал добавляется в список, мы знаем его количество вложенных интервалов. Это просто количество элементов справа от него, когда он был добавлен в список.
 mandy18 окт. 2012 г., 09:18
Большое спасибо! Я на самом деле приблизился к этому. Первоначально я отсортировал все точки и перебрал их от наименьшего к наибольшему. В то же время я держал активный набор для представления интервалов, чьи начальные точки я видел, но не конечные точки. Моя проблема заключалась в том, что когда я увидел конечную точку, я не знал, как обновить счетчики интервалов, в которых завершенный интервал находился внутри, за время, превышающее O (n). Но твой дополнительный трюк решает это довольно элегантно! Еще раз спасибо!

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

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

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

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

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

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

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

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

Ваш ответ на вопрос