UVA 11926 Multitasking

uva.onlinejudge.org/external/119/11926.pdf

Este problema puede ser resuelto usando un árbol de Fenwick, pero en una forma no convencional. Crearemos el árbol del tamaño de la máxima duración de una tarea (10^6), y lo vamos a utilizar para contar cuantas tareas se están ejecutando en un momento dado.

Cada tarea esta representada por el inicio (s) y el final (e). Supongamos que en la posición s del BIT insertamos 1. De esta manera, cuando consultemos cuantas tareas se están ejecutando en el momento s, tendremos 1. Pero dada la estructura de responsabilidades del BIT, si consultamos en cualquier momento mayor que s, también tendremos que hay 1 tarea activa, porque se acumula a lo largo del árbol.  La forma de contrarrestar esto, es insertar -1 en la posición e, para que no se propague el valor de la posición e en adelante. De esta manera, cuando consultemos el intervalo [s, e] tendremos 1 tarea activa, y si consultamos fuera del intervalo, tendremos 0.

Con esta idea, cada vez que tengamos una tarea, consultamos su inicio y su final en el BIT para saber si hay alguna ejecutándose en estos momentos, y si es así, tenemos un conflicto. De lo contrario, la insertamos en el árbol haciendo update(s, 1) y update(e, -1). Hay que tener cuidado especial con los puntos de inicio y final, ya que dos tareas si pueden “tocarse”, pero no pueden solaparse.

Anuncios

Comentar

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s