Алгоритм нахождения интервалов внутри массива

Question

У меня есть список, который содержит n интервалов [0,1]

каждый интервал выглядит как [a(i),b(i)] 0<=a(i)<b(i)<=1 , i = 1...n

Мне нужно найти эффективный алгоритм, определяющий для каждого из n интервалов, содержится ли он в других интервалах.

Я пробовал много вариантов, но я могу найти только один в O (n ^ 2)

Есть предложения?

Answer 1

Подсказка: сортировка списка.

Answer 2

1. Сортировка интервалов в соответствии с их начальными точками, разрывающими связи, так что более ранние конечные точки появляются позже
2. Обратите внимание, что в отсортированном порядке для каждого элемента e интервал, содержащий e, может существовать только слева от него.
3. Следовательно, линейное сканирование с левой стороны отслеживает максимальную конечную точку, наблюдаемую до сих пор. На любом этапе, если конечная точка текущего интервала меньше максимальной конечной точки, мы нашли интервал, который содержится внутри некоторого другого.

Answer 3

Предположим, что есть только один интервал [0,1]. Добавьте его, если его нет в вашем списке просто для удобства.

Сортировка конечных точек. Если две конечные точки равны, сортируйте их в обратном порядке по соответствующим правым конечным точкам. Таким образом, [0,1, 0,2], [0,1, 0,3] будут отсортированы по 0,1, 0,1, 0,2, 0,3, где первый 0,1 идет со вторым интервалом. Точно так же, если правильные конечные точки равны.

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

Сканирование отсортированных конечных точек. Как вы делаете, построить дерево. Используйте [0,1] в качестве корня. Узлы могут быть красными или зелеными. Они начинаются как красные. Таким образом, корневой узел изначально красный.

Идея дерева состоит в том, что, в конечном счете, если один интервал содержит другой, он будет его предком в дереве. Если два интервала не перекрываются или частично перекрываются, они будут находиться в разных ветвях, и их единственным общим предком будет корень или какой-то другой интервал, содержащий их оба.

Когда встречается каждая левая конечная точка, она добавляется в предварительное местоположение в дереве, добавляя красный узел для своего интервала к текущему узлу дерева. Таким образом, первая конечная точка, с которой мы сталкиваемся, приводит к добавлению соответствующего интервала под корнем, и она становится текущим узлом. Таким образом, до того, как будет обнаружена его правая конечная точка, к узлу дерева может быть присоединено несколько узлов.

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

Мы продолжаем этот процесс, пока не доберемся до конечной точки 1.0. На данный момент дерево завершено. все узлы зеленые. Узлы под каждым узлом представляют интервалы, которые содержит соответствующий интервал.