Perguntei há alguns dias, uma pergunta sobre como transformar um problema de agendamento de aulas na universidade em um problema booleano de satisfação.

(Escalonamento de Classes com Satisfação Booleana [Redução de Tempo Polinomial])

Recebi uma resposta do @Amit, que era muito elegante e fácil de codificar. Basicamente, sua resposta foi assim: em vez de considerar cursos, ele considerou intervalos de tempo.

Portanto, no i-ésimo curso, ele indicou todos os intervalos possíveis para esse curso. E obtemos uma solução quando há pelo menos 1 intervalo verdadeiro para cada curso e quando nenhum intervalo se sobrepõe.

Este método funciona muito bem quando consideramos apenas cursos e nada mais. Eu o generalizo codificando a sala dentro do intervalo.

por exemplo, em vez de [8-10] dizer que um curso pode acontecer entre as 8h e as 10h.

Eu usei [0,00801 - 0,01001] para dizer que um curso pode acontecer entre as 8h e as 10h na sala 1.

Tenho certeza de que você está vagando "por que usar o dobro?" bem, porque aqui vem o meu problema:

Para continuar a generalizar esse método, codifico também o n ° do professor nesse intervalo.

Eu costumava [1.00801 - 1.01001] dizer que um curso pode acontecer entre as 8h e as 10h na sala 1 e ser ministrado pelo professor n ° 1.

Aqui está o que eu tenho por enquanto:

assim [1.008XX - 1.010XX] pode acontecer ao mesmo tempo que [2.008YY - 2.010YY], o que é verdade, se o professor 1 estiver ensinando na sala X entre as 8h e as 10h, o professor 2 também poderá ensinar Y entre 8h e 10h, se e somente se o quarto estiver disponível.

O problema é: com este método, não posso garantir que XX e YY serão diferentes e que YY estará disponível, porque [1.008XX - 1.010XX] não se sobrepõem [2.008XX - 2.010XX], então, por enquanto, o solucionador considere isso possível.

E ainda não tenho idéia de como garantir isso, usando esse método de intervalo ... Eu preciso de uma maneira de codificar {Interval, room and teacher-id} para que:

um professor não pode estar em 2 lugares no mesmo intervalo.não pode haver 2 professores na mesma sala pelo mesmo intervalo.há pelo menos 1 intervalo verdadeiro por curso.

Agradecemos antecipadamente a sua ajuda, Atenciosamente!

Questão a seguir: Programação de classe para satisfação booleana [Redução de tempo polinomial] Parte final