Подсчитать количество интервалов, содержащих другой интервал?

Даны два списка, каждый из которых содержит N интервалов (подмножество числовой прямой), каждый интервал имеет форму начальной и конечной точек. Сколько пар этих интервалов из одного списка содержат интервалы из другого списка?

Например:

Если список A равен {(1,7), (2,9)}, а список B - {(3,6), (5,8)}

Тогда количество пар, где у A есть интервал, содержащий интервал в B, будет 3 пары:

(1,7),(3,6)
(2,9)(3,6)
(2,9)(5,8)

Цель состоит в том, чтобы выстрелить за O (n log n).

В настоящее время мой алгоритм состоит в том, чтобы сначала отсортировать по координате x и принять это как один список. Затем отсортируйте список по координате y и посчитайте инверсии между двумя списками. Но у меня вопрос: почему это работает? Любое понимание будет оценено.

В настоящее время я визуализирую следующий геометрический образ (где каждое пересечение линий является счетчиком инверсии числа):

введите описание изображения здесь

Примечание: я не уверен, как проверять инверсии в списке списка. Просто пытаюсь найти подход, который дал бы O (n log n). Если есть другие подходы, рад выслушать предложения.


optimization algorithm intervals divide-and-conquer inversion
person tattvabodha    schedule 08.02.2016    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Отвечу на первый вопрос, почему работает решение с инверсией. Во-первых, проясню одну вещь. Вы не должны считать все инверсии (пересечения линий), а только те, которые происходят между элементом из списка A и элементом из списка B. В вашем примере разницы нет, но предположим, что A = {(1,7), (2,5)} и B = {(3,6), (5,8)}. Если мы визуализируем этот случай, как в вашем примере, будет 2 пересечения, но есть только 1 пара, которую мы ищем, то есть (1,7), (3,6).

Теперь предположим, что у нас есть 2 интервала: I1=(x1,y1) и I2=(x2,y2). I2 включен в I1. Значит, x1 <= x2 и y1 >= y2. Теперь, если вы отсортируете список интервалов по x, тогда I1 всегда будет перед I2. Аналогично, если вы отсортируете список интервалов по y, то I1 всегда будет после I2. Это также означает, что если мы соединим I1, I2 в первом списке с I1, I2 во втором списке, тогда линии должны пересекаться.

Однако предположим, что x1 <= x2 и y1 < y2. Теперь I1 будет перед I2 в первом и втором списках. Если мы соединим I1, I2 в первом списке с I1, I2 во втором списке, то линии никогда не пересекутся. Такая же ситуация, если x1 > x2 и y1 >= y2

Вот визуализация этих случаев:

person Michał Komorowski    schedule 08.02.2016

arrow_upward
2
arrow_downward

Если вы решите попробовать также подход дерева / пояса, я объясню, как это может работать. Для вашей задачи вам понадобится не 2D, а одномерная интервальная карта или даже сетка. Выберем сетку, потому что она более четкая.

Предположим, что ваши пары представляют собой целые числа от 1 до 100. Тогда вы можете позволить себе иметь один массив размером 100. Каждая ячейка из массива содержит пустой набор (упорядоченный список). См. Картинку ниже:

введите описание изображения здесь

Теперь приступаем к добавлению интервалов в сетку. Мы добавляем 1 во все продажи сетки между 1,7 и 2 во всех ячейках сетки между 2,9 (1,2 - это идентификаторы, которые мы увеличиваем на 1 с каждым вставленным интервалом, вставка таким образом неэффективна, но это можно исправить).

Как теперь проверить интервалы из B? Мы просто получаем каждый идентификатор из первой ячейки и проверяем, находится ли он также во второй ячейке. Поскольку ячейки установлены, проверка занимает O (log n). В худшем случае нам понадобится n O (log n) операций, чтобы проверить количество перекрывающихся интервалов, которое один интервал из B имеет внутри A.

Это можно расширить, чтобы использовать карту интервалов вместо сетки (если числа не являются маленькими целыми числами). Также, если у вас есть фиксированное количество интервалов в A и нет требований к памяти, O (logN) может стать O (1), если мы заменим наборы, например, массивами.

person Baj Mile    schedule 08.02.2016
comment
можно ли этого достичь без использования древовидной структуры? - person tattvabodha; 08.02.2016
comment
да. Это идея. Вы можете работать с интервалами вместо точек. Попробуйте сначала разобраться в этом в 1D. Вместо того, чтобы иметь двоичное дерево (набор), вы можете сделать interval_tree. Затем это дерево можно использовать, чтобы найти в logN интервал, которому принадлежит точка. - person Baj Mile; 08.02.2016
comment
Извините, я неправильно прочитал, что ваша проблема не в точках (x, y) в 2D. Вам не нужно квадродерево. - person Baj Mile; 09.02.2016