Enunciado:
No problema de seleção de atividades, temos S = { a₁, a₂, ..., a_n } onde a_i é a atividade com tempo de inicio s_i e termino f _i. Deseja-se selecionar um subconjunto de tamanho máximo de atividades mutuamente compatíveis , isto é, que não se sobreponham no tempo. Considere os seguintes algoritmos gulosos para sua resolução:

	Algoritmo 1					Algoritmo 2
1	Greedy-Activity-Selector(S, f)				1	Greedy-Ivan-Activity-Selector(S, f)
2		n <- comprimento[S]			2		n <- comprimento[S]
3		A <- { a1 }			3		A <- { an }
4		i <- 1			4		i <- n
5		For m <- 2 to n do			5		for m <- (n –1) down to 1 do
6			if sm >= fi then		6			if fm <= si then
7				A <- A U { am }	7				A <- A U { am }
8				i <- m	8				i <- m
9		return A			9		return A

Observe que a diferenca está nas linhas 3 a 6.
Assinale a alternativa CORRETA:

A) O algoritmo 1 funciona para todos os casos e o algoritmo 2 funciona somente para alguns casos.
B) O algoritmo 1 funciona para todos os casos e o algoritmo 2 nao funciona para nenhum caso.
C) Os dois algoritmos funcionam para todos os casos em que as atividades estão ordenadas por tempo de TÉRMINO monotonicamente crescente. Eles apenas invertem as ordens de comparação, produzindo, portanto, o mesmo resultado.
D) O algoritmo 1 funciona sempre que as atividades estejam ordenadas por tempo de TÉRMINO monotonicamente crescente e o algoritmo 2, sempre que estejam ordenadas por tempo de INÍCIO monotonicamente crescente.
E) NDA

Autor: Ivan Brunetto