Hace unos días, hice una pregunta sobre cómo transformar un problema de programación de clases universitarias en un problema de satisfacción booleana.

(Programación de clases a la satisfacción booleana [Reducción del tiempo polinómico])

Recibí una respuesta de @Amit, que era muy elegante y fácil de codificar. Básicamente, su respuesta fue así: en lugar de considerar cursos, consideró intervalos de tiempo.

Entonces, para el i-ésimo curso, él solo acusó a todos los intervalos posibles para este curso. Y obtenemos una solución cuando hay al menos 1 intervalo verdadero para cada curso y cuando ningún intervalo se superpone a otro.

Este método funciona muy bien cuando consideramos solo cursos y nada más. Lo generalizo codificando la habitación dentro del intervalo.

por ejemplo, en lugar de [8-10] para decir que un curso puede ocurrir entre las 8 a.m. y las 10 a.m.

Usé [0.00801 - 0.01001] para decir que un curso puede ocurrir entre las 8 am y las 10 am en la sala 1.

Estoy seguro de que actualmente estás divagando "¿por qué usar el doble?" bueno, porque aquí viene mi problema:

Para continuar generalizando este método, codifico también el n ° del profesor en este intervalo.

Utilicé [1.00801 - 1.01001] para decir que un curso puede ocurrir entre las 8 am y las 10 am en la sala 1 y que el maestro n. ° 1 enseñe.

Esto es lo que tengo por ahora:

así [1.008XX - 1.010XX] puede suceder al mismo tiempo que [2.008YY - 2.010YY], lo cual es cierto, si el maestro 1 está enseñando en la sala X entre las 8 am y las 10 am, el maestro 2 también puede enseñar en Y entre las 8am y las 10am, si y solo si la habitación está disponible.

El problema es: con este método no puedo asegurar que XX e YY serán diferentes y que YY estará disponible, porque [1.008XX - 1.010XX] no se superponen [2.008XX - 2.010XX], así que por ahora, el solucionador Considera esto posible.

Y todavía no tengo idea de cómo asegurar esto, usando este método de intervalo ... Necesito una forma de codificar {Interval, room and teacher-id} para que:

un maestro no puede estar en 2 lugares en el mismo intervalo.no puede haber 2 profesores en la misma sala durante el mismo intervalo.hay un mínimo de 1 intervalo verdadero por curso.

Gracias de antemano por su ayuda, Saludos cordiales!

Siguiente pregunta: Programación de clases a satisfacción booleana [Reducción del tiempo polinómico] Parte final