Use un enfoque de línea de barrido para reducir la dimensionalidad del problema. Cada rectángulo tendrá dos eventos: uno cuando ingresa a la línea de barrido y otro cuando sale de la línea de barrido.
Ahora tenga en cuenta que en cada punto, hay un conjunto de rectángulos que se cruzan con la línea de barrido. Por lo tanto, ahora estamos buscando la versión unidimensional del problema. Cada rectángulo define un intervalo en la línea de barrido y queremos encontrar el punto en la línea de barrido que está contenido en el número máximo de intervalos.
La forma más obvia de hacer esto es usar nuevamente una línea de barrido. Deje que cada intervalo en la primera línea de barrido tenga un evento de entrada y un evento de salida. Nuestra segunda línea de barrido pasa por cada evento en orden, haciendo un seguimiento de cuántos intervalos lo intersecan. Devuelve el punto en el que este número está al máximo.
- Dadas las ventajas de usar el ternario como base de las computadoras, y la experiencia de los soviéticos, ¿por qué no hay computadoras cuaternarias ternarias o imaginarias? Knuth aprobó el ternario y propuso el cuaternario como eficiente para la computación científica.
- ¿Cuál es la diferencia entre funciones y acciones en QTP?
- ¿De qué manera las matemáticas son similares a la codificación?
- ¿Cuál es el polinomio más pequeño que puede atravesar todos los conjuntos de n puntos? ¿Hay uno?
- ¿Existe un algoritmo eficiente para encontrar el primo más pequeño mayor que N?
Este enfoque requiere tiempo [matemático] O (n \ log n) [/ matemático] para cada problema unidimensional. Como hay eventos [math] O (n) [/ math] para la primera línea de barrido, hay iteraciones [math] O (n) [/ math], lo que resulta en un tiempo de ejecución de [math] O (n ^ 2 \ log n) [/ math].
Claramente podemos hacerlo mejor: ¡no estamos aprovechando la primera línea de barrido en absoluto!
En lugar de resolver el problema unidimensional en cada evento, simplemente debemos actualizar nuestra solución al problema unidimensional. Así es cómo. Tenga en cuenta que en cualquier punto hay intervalos [matemáticos] O (n) [/ matemáticos] en nuestro problema unidimensional. Estos segmentan la línea de barrido en [matemática] O (n) [/ matemática] intervalos disjuntos. Solo necesitamos realizar un seguimiento de estos intervalos y, para cada intervalo, realizar un seguimiento de cuántos rectángulos lo contienen. Una vez que resolvemos esto, es fácil actualizarlo cuando un rectángulo entra o sale. Cada vez que un rectángulo entra o sale, se crean intervalos [matemáticos] O (1) [/ matemáticos], los intervalos [matemáticos] O (1) [/ matemáticos] se destruyen (o se unen) y varios intervalos en un rango tienen sus cuentas incrementadas o disminuidas.
Me imagino que hay varias formas de implementar algo como esto. Por ahora, lo que me viene a la mente son los árboles extendidos. Representamos cada intervalo como un nodo en el árbol de visualización, con el recuento como clave. La inserción y eliminación se amortizan [matemática] O (\ log n) [/ matemática]. La parte difícil es aumentar o disminuir las claves de un rango de nodos de manera eficiente. Podemos hacer esto con un buen truco: aumentar cada nodo con un campo ‘extra’, que indica cuánto agregar a las claves de los nodos en su subárbol. Se puede demostrar que mantener este campo no cambia el tiempo de ejecución amortizado. Con este campo, podemos aumentar o disminuir un rango de nodos colocando primero todos los nodos en un subárbol (separe el mínimo del subárbol, divídalo del árbol principal, luego separe el máximo del subárbol, divídalo), actualizando el campo ‘extra’ de su raíz, y luego uniendo los árboles en uno nuevamente.
Ahora, cada evento para la línea de barrido se amortiza [math] O (\ log n) [/ math] lo que lleva al tiempo de ejecución completo deseado [math] O (n \ log n) [/ math].
