7
Hier ist eine interessante Frage: Gegeben eine Reihe von N Intervallen ([Start, Ende]), verwenden Sie einen Intervallbaum, um die maximale Anzahl überlappender Intervalle zu finden.Maximale Intervallüberlappungen unter Verwendung eines Intervallbaums
Eine similar question auf StackOverflow lieferte eine O (N) -Lösung, aber wenn wir die Intervalle in einen Intervallbaum vorverarbeiten können, können wir vielleicht die Lösung in logarithmischer Zeit finden.
In der Tat schlägt ein Übungsproblem in dem Buch "Introduction to Algorithms" von Cormen et al. Vor, dass dies möglich ist, indem ein rot-schwarzer Intervallbaum erweitert wird. Irgendwelche Ideen wie das gemacht werden kann?
Sind Sie an Operationen interessiert, wie 'Add (x, y) - fügen Sie dem Baum ein Intervall hinzu,' Query() - finden Sie die maximale Anzahl überlappender Intervalle? Wollen Sie auch 'Del (x, y) - löschen Sie das Intervall [x, y] aus dem Baum? – IVlad
Wenn die Intervalle in einem ausgeglichenen Intervallbaum angeordnet sind, wie der in Cormens Buch beschriebene, wissen wir bereits, dass Add (Intervall) und Delete (Intervall) in O (lg N) -Zeit ausgeführt werden. Also würde ich gerne wissen, wie man diesen Baum benutzt, um die maximale Anzahl von überlappenden Intervallen in vorzugsweise 0 (lg N) Zeit zu finden. – stackoverflowuser2010
Können Sie Überlappungen definieren? Das heißt, meinst du eine Reihe von Intervallen mit einem gemeinsamen Punkt oder meinen Sie eine Menge von Intervallen, so dass es einen überlappenden Pfad zwischen jedem Paar gibt? – Rafe