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.

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

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