MO417 - Ata de exercício resolvido em aula

Aulas de 30/04/2009, 5a feira, e 05/05/2009, 3a feira

Livro: Algoritmos, Teoria e Prática - Tradução da 2a edição americana
Capítulo 16 - Algoritmos Gulosos

Exercício 16.2-5:
Descreva um algoritmo eficiente que, dado um conjunto {x1, x2, ..., xn} de pontos na reta real, determine
o menor conjunto de intervalos fechados de comprimento unitário que contenha todos os pontos dados.
Mostre que seu algoritmo é correto.

Resolução:
(Algoritmo proposto pelo colega Raoni Teixeira.)
    MENOR_CONJUNTO_INTERVALOS(A)
     1 n ← tamanho[A]
     2 i ← 1
     3 S ← ∅ // conjunto vazio
     4 HEAP_SORT(A)
     5 while (i ≤ n) do
     6   S ← S ∪ {[A[i], A[i]+1]}
     7   p ← i
     8   i ← i + 1
     9   while (i ≤ n) and (A[i] ≤ A[p]+1) do
    10     i ← i + 1
    11 return S
Comentários:
O algoritmo funciona da seguinte maneira. Após a ordenação dos pontos na linha 4,
o primeiro intervalo unitário fechado é dado por [A[1], A[1]+1]. O algoritmo avança
testando cada ponto do vetor. Se um dado A[i] for o ponto mais à esquerda não contido
em algum intervalo já existente, um novo intervalo é formado como [A[i], A[i]+1],
e assim sucessivamente, até o último ponto do vetor. Cada intervalo formado é incluído
no conjunto de intervalos S, que é retornado pelo algoritmo.
O algoritmo está correto, uma vez que o ponto mais à direita do conjunto (o último ponto)
deve estar contido em algum intervalo. No melhor caso, será no primeiro intervalo,
[A[1], A[1]+1]. No pior caso, será no intervalo iniciado no próprio ponto, ou seja,
[A[n], A[n]+1].

[Redator: Fábio de Souza Azevedo]