Nós temos uma lista de intervalos do formulário[ai, bi]. Para cada intervalo, queremos contar o número de outros intervalos que estão aninhados dentro dele.

Por exemplo, se tivéssemos dois intervalos,A = [1,4] eB = [2,3]. Então a contagem paraB seria0 como não há intervalos aninhados paraB; e a contagem paraA seria1 ComoB cabe dentroA.

Minha pergunta é, existe umasub- O(n2) algoritmo para este problema onden é o número de intervalos?

EDITAR: Aqui estão as condições que os intervalos se encontram. Os pontos finais dos intervalos são números de ponto flutuante. O limite inferior para oi's / bié 0 e o limite superior é o que for o máximo de flutuação. Além disso, existe a condição de quei <bi, então não há intervalos de comprimento 0.