Mamy listę interwałów formularza[ai, bi]. Dla każdego przedziału chcemy policzyć liczbę innych przedziałów, które są w nim zagnieżdżone.

Na przykład, jeśli mieliśmy dwa przedziały,A = [1,4] iB = [2,3]. Potem liczyćB byłoby0 ponieważ nie ma zagnieżdżonych interwałów dlaB; i liczyć zaA byłoby1 tak jakB pasuje do środkaA.

Moje pytanie brzmi, czy istniejepod- O(n2) algorytm dla tego problemu gdzien to liczba interwałów?

EDYTOWAĆ: Oto warunki, w jakich odstępy się spotykają. Punkty końcowe przedziałów są liczbami zmiennoprzecinkowymi. Dolny limit dla ai's / bijest 0, a górny limit jest jakimkolwiek maksymalnym pływakiem. Istnieje również warunek, że ai <bi, więc nie ma przedziałów długości 0.