Sub O (n ^ 2) -Algorithmus zum Zählen verschachtelter Intervalle?

Wir haben eine Liste von Intervallen des Formulars[ai, bi]. Für jedes Intervall möchten wir die Anzahl der anderen Intervalle zählen, die darin verschachtelt sind.

Wenn wir zum Beispiel zwei Intervalle hätten,A = [1,4] undB = [2,3]. Dann die Zählung fürB wäre0 da es für keine verschachtelten Intervalle gibtB; und die Zählung fürA wäre1 wieB passt inA.

Meine Frage ist, gibt es eineUnter- O(n2) Algorithmus für dieses Problem, won ist die Anzahl der Intervalle?

BEARBEITEN: Hier sind die Bedingungen, die die Intervalle erfüllen. Die Endpunkte der Intervalle sind Gleitkommazahlen. Die Untergrenze für die ais / bi's ist 0 und die Obergrenze ist das Maximum des Floats. Es gibt auch die Bedingung, dass ai <bi, also keine Intervalle der Länge 0.

Antworten auf die Frage(2)

Ihre Antwort auf die Frage