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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этот последний алгоритм O (n log n) по тем же причинампростой алгоритм " было.

[Обновить]

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

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

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

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

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

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

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

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

Вот O (N * LOG (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.

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