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.