O problema das trocas - você consegue?

[spotify 0]

Pessoal, sabem me indicar um referencial teórico para que consiga resolver um problema proposto por meu professor?

 

O contexto é bem simples.

 

Uma empresa multinacional tem diversas unidades por todo o mundo. Ela permite que seus funcionários troquem de cidade e mantenham seu emprego desde que este funcionário tenha o mesmo cargo com o outro da troca.

 

Tenho que chegar a um algoritmo para resolver 3 problemas.

 

A) Encontrar um interesse de troca em comum quando houver. Pessoa da cidade A quer ir pra B e vice e versa.

B) Encontrar uma vaga quando houver triangulação. Pessoa da cidade A vai pra B, pessoa da cidade B vai para C e pessoa da cidade C vai para A.

C) O mesmo que triangulação, porém em N níveis. Descobrir vagas quando em mais de 3 níveis (triangulação). Isto é possível?

 

 

Alguém já resolveu este problema? Se sim, teriam um referencial teórico para me passar? Preciso resolver este problema em forma de algoritmo e estou perdido. Toda ajuda é bem vinda.

[NoSlake 56]

[Ryokusei 28]

"A) Encontrar um interesse de troca em comum quando houver. Pessoa da cidade A quer ir pra B e vice e versa."

 

Verifique se há algum indicador no objeto de cada funcionário indicando que ele quer mudar. Faça isso varrendo por cargo, pois a troca só será efetuada se dois de mesmo cargo desejam trocar. Armazene os que desejam trocar de cargo em pares listas, uma para cada cidade que possui funcionários que desejam trocar para a outra cidade do par.

Nisso você já encontrou os interesses de troca em comum.

 

"B) Encontrar uma vaga quando houver triangulação. Pessoa da cidade A vai pra B, pessoa da cidade B vai para C e pessoa da cidade C vai para A.

C) O mesmo que triangulação, porém em N níveis. Descobrir vagas quando em mais de 3 níveis (triangulação). Isto é possível?"

Tendo as listas descritas acima em mãos, use o conceito e implementação de Union Find para comprimir a quantidade de listas e remover redundâncias. Após isso, verifique triangulações pegando um elemento de cada lista por vez. Fazendo desse jeito, você tem o item B e C feitos num processo só.