Solução Escalonamento Ótimo

0 Flares Facebook 0 0 Flares ×

Solução por Lucca Siaudzionis

Estes problemas que envolvem executar certas tarefas numa determinada ordem de prioridade geralmente estão relacionados a Ordenação Topológica. Há vários algoritmos para resolver um problemas de Ordenação Topológica (este artigo da Wikipédia explica bem o assunto). O problema Escalonamento Ótimo é mais difícil que uma simples ordenação topológica porque ele requer que as tarefas sejam, também, executadas por ordem crescente.

Pois bem, quando estamos resolvendo uma Ordenação Topológica, sempre temos uma "sacola" que contém todas as tarefas que já podem ser executadas a partir de agora (i.e. não precisam de nenhuma tarefa anterior ou as tarefas que necessita já foram executadas). Para imprimirmos sempre os número desta sacola em ordem crescente, podemos usar uma estrutura chama Fila de Prioridade (também conhecida como Heap). Heap (artigo da Wikipédia) é uma árvore binária em que o pai é sempre maior (no caso de uma max heap) ou menor que os filhos (no caso de uma min heap). Com isso, sabemos que, a qualquer instante, a raiz da árvore é o maior número na max heap (ou o menor, no caso da min heap).

Na biblioteca <queue> de C++ já há implementada a priority_queue, para que se possa usar a Heap sem você ter que montar ela inteira. Porém, recomendo que cada pessoa saiba montar uma heap. Vou disponibilizar o código nos dois casos.

Usando a estrutura montada:

Montando a própria estrutura:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: