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.