7
Aquí hay una pregunta interesante: dado un conjunto de N intervalos ([inicio, final]), utilice un árbol de intervalos para encontrar el número máximo de intervalos superpuestos.Superposiciones máximas de intervalo usando un árbol de intervalos
A similar question en StackOverflow proporcionó una solución O (N), pero si podemos preprocesar los intervalos en un árbol de intervalos, quizás podamos encontrar la solución en tiempo logarítmico.
De hecho, un problema de ejercicio en el libro "Introducción a los algoritmos" de Cormen, et al. Sugiere que esto es posible mediante el aumento de un árbol de intervalos rojo-negro. ¿Alguna idea de cómo se puede hacer esto?
¿Le interesan las operaciones como 'Agregar (x, y) - agregar un intervalo al árbol',' Consultar() - encontrar el número máximo de intervalos superpuestos'? ¿Desea también 'Del (x, y) - borrar el intervalo [x, y] del árbol'? – IVlad
Si los intervalos están organizados en un árbol de intervalos balanceados como el proporcionado en el libro de Cormen, entonces ya sabemos que Agregar (intervalo) y Eliminar (intervalo) se ejecutan en O (lg N) tiempo. Entonces me gustaría saber cómo usar este árbol para encontrar el número máximo de intervalos superpuestos en preferiblemente el tiempo O (lg N). – stackoverflowuser2010
¿Se puede definir la superposición? Es decir, ¿te refieres a un conjunto de intervalos con un punto en común o te refieres a un conjunto de intervalos tales que hay una ruta de superposición entre cualquier par? – Rafe