O problema computacional da colocação de professores, pelo contrário, é extremamente simples, ou "linear". Cada professor é ordenado numa lista em função da sua qualificação em diversos itens que por sua vez têm prioridades relativas bem definidas. Uma vez a lista definida, o 1º professor, que se candidatou a uma lista de escolas ordenada pela sua preferência, vê, pela ordem que ele indicou, se há vaga nessa escola. Se sim, a vaga é-lhe atribuída, deixa de estar disponível para os seguintes, e o algoritmo passa ao professor seguinte da lista. O problema é linear, portanto. Mas para o computador, não para o programador!!! E isto porque há imensos itens de ordenação, acrescendo que há casos em que o professor concorre a uma "zona", deixando portanto ao "computador" a prioritização das escolas da zona a escolher.
O Pinto de Sá parte do princípio que ao longo do processo de colocação a lista de escolas vagas é fixa. Como eu expliquei anteriormente, isto só é verdade num universo em que nenhum professor está previamente alocado a uma escola (num universo em que nenhum professor é efectivo). Neste concurso, os professores efectivos podem pedir destacamento para outra escola. Isto significa que a colocação de um professor efectivo altera a lista das escolas vagas e o problema não pode ser resolvido sequencialmente. O algorítmo tem que fazer duas coisas em simultâneo: colocar os professores e determinar as escolas com vagas. E estas duas coisas são interdependentes.
