Tenemos una lista de intervalos del formulario.[ai, bi]. Para cada intervalo, queremos contar el número de otros intervalos que están anidados dentro de él.

Por ejemplo, si tuviéramos dos intervalos,A = [1,4] yB = [2,3]. Entonces la cuenta paraB sería0 Como no hay intervalos anidados paraB; y la cuenta paraA sería1 comoB encaja dentroA.

Mi pregunta es, ¿existe unsub- O(n2) algoritmo para este problema donden es el numero de intervalos?

EDITAR: Estas son las condiciones que cumplen los intervalos. Los puntos finales de los intervalos son números de punto flotante. El límite inferior para la ais / bis es 0 y el límite superior es lo que sea el máximo de flotación. Además, existe la condición de que uni <bi, por lo que no hay intervalos de longitud 0.