Algoritmo Guloso para Problemas de Intervalos e Programacao de Tarefas

Guloso 1 Resolva os problemas a seguir usando o método Guloso Evidencie as 5 etapas do processo de criação e calcule a complexidade de tempo do algoritmo resultante a Dado um conjunto x1 xN de pontos da reta real determine o menor conjunto de intervalos fechados de tamanho unitário que contenham todos os pontos Ex para os pontos 1 22 31 43 53 o conjunto de intervalos 12 23 34 45 56 contém todos os pontos mas não é o menor conjunto que consegue fazer isto pela existência de 12 2131 4353 b Há uma série de N tarefas e uma recompensa de Ri reais se a tarefa i for iniciada no máximo até a hora Ti para todo 1 i N Cada uma destas tarefas leva 1h para ser executada a primeira tarefa começa na hora zero e elas podem ser executadas em qualquer ordem Faça uma programação das tarefas de modo a maximizar a receita Ex se N 5 T1 1 T2 2 T3 3 T4 3 T5 4 R1 1 R2 2 R3 2 R4 3 R5 1 a programação de tarefas 4 3 2 1 5 tem receita 320005 mas não é ótima pela existência da programação 1 2 4 5 3 com receita 123107