Intervalos disjuntos

Imagine que vários eventos (feiras, congressos, etc.) querem usar um certo centro de convenções. Cada evento i gostaria de usar o centro durante um intervalo de tempo que começa num dia a[i] e termina num dia b[i]. Dois eventos são compatíveis se seus intervalos de tempo são disjuntos. A administração do centro de convenções quer atender o maior número possível de eventos que sejam compatíveis dois a dois. Este é um exemplo do problema da coleção disjunta máxima de intervalos.

Exemplo A.  Cada linha horizontal da figura representa um intervalo de tempo (o menor dura 5 dias e o maior dura 26 dias). A cor mais escura identifica uma coleção de intervalos disjuntos dois a dois.
figs/mine/livrinho-intervals-noweights-1.png

Esta página discute um algoritmo guloso para o problema da coleção disjunta máxima de intervalos. A página foi inspirada no capítulo 16 de CLRS, onde o problema é chamado Activity-Selection Problem.

Formalização do problema

Suponha que a[p .. r] e b[p .. r] são dois vetores de números inteiros positivos tais que a[i] ≤ b[i] para cada i. Portanto, para cada i, o intervalo a[i] .. b[i] não é vazio. Diremos que o par (a, b) de vetores é uma coleção de intervalos.

Os índices p, p+1, … , r são os nomes dos intervalos da coleção. Portanto, podemos usar expressões como a coleção de intervalos { p, p+1, … , r } para falar da coleção de intervalos (a, b).

Para cada intervalo i, diremos que a[i] é o início do intervalo e b[i] é o término do intervalo. Um intervalo i é anterior a um intervalo k se  b[i] < a[k],  ou seja, se i termina antes do início de k. Nas mesmas condições, k é posteriori. Dois intervalos são disjuntos se e somente se o primeiro é anterior ou posterior ao segundo.

Uma subcoleção da coleção de intervalos { p, … , r } é disjunta se seus elementos são disjuntos dois a dois. Uma subcoleção disjunta é máxima se não existe uma maior. Em outras palavras, uma subcoleção disjunta X é máxima se não existe subcoleção disjunta Y tal que tal que │Y│ > │X│.

Problema da Coleção Disjunta Máxima de Intervalos:  Encontrar uma subcoleção disjunta máxima de uma coleção (a[p .. r], b[p .. r]) de intervalos.

Usaremos a abreviatura SCD para a expressão subcoleção disjunta. Nosso problema consiste, então, em encontrar uma SCD máxima de uma coleção de intervalos.

Uma SCD da coleção de intervalos { p, … , r } poderia ser representada por seu vetor característico x[p .. r]. Mas nesta página trataremos cada SCD como um mero subconjunto de { p, … , r }.

Exemplo B:  Considere a coleção de 8 intervalos representada na figura. (Mesma coleção do exemplo A.) A subcoleção { 7, 8 } é disjunta. A subcoleção { 1, 2, 6 } também é disjunta. A primeira não é uma SCD máxima pois a segunda é maior. A segunda é máxima? Existe uma SCD com quatro intervalos?

  1 2 3 4 5 6 7 8
a
b
6
15
25
30
9
15
23
28
7
16
18
24
30
34
1
26
 
 

Exercícios 1

  1. ★ Seja S = { p, … , r } uma coleção de intervalos e X uma SCD maximal de S. (Portanto, nenhum superconjunto próprio de X é uma SCD de S.) É verdade que X é uma SCD máxima de S?
  2. Mostre que uma instância do problema da coleção disjunta máxima pode ter mais de uma solução.
  3. ★ A duração de um intervalo a[i] .. b[i] é o número b[i] − a[i]. É verdade que toda SCD máxima de uma coleção de intervalos contém um intervalo de duração mínima? É verdade que alguma SCD máxima tem essa propriedade?
  4. É verdade que toda SCD máxima de uma coleção de intervalos contém um intervalo de término mínimo? É verdade que alguma SCD máxima tem essa propriedade?
  5. É verdade que toda SCD máxima de uma coleção de intervalos contém um intervalo de início mínimo? É verdade que alguma SCD máxima tem essa propriedade?

Um algoritmo guloso

O problema da SCD máxima admite um algoritmo guloso. Cada iteração do algoritmo escolhe um intervalo de término mínimo e remove da coleção todos os intervalos que não são posteriores ao intervalo escolhido.

Em outras palavras, o algoritmo consiste no seguinte: Cada iteração começa com uma subcoleção D da coleção de intervalos dada. Em cada iteração, o algoritmo escolhe um intervalo de término mínimo dentre os que são posteriores aos de D e acrescenta esse intervalo a D.  O algoritmo é guloso porque escolhe, repetidamente, o intervalo mais apetitoso da iteração sem medir as consequências dessa escolha.

Exemplo C.  Uma aplicação do algoritmo guloso ao exemplo da figura (mesma coleção dos exemplos A e B) pode produzir a subcoleção destacada em cinza mais escuro.
figs/mine/livrinho-intervals-noweights-1.png

É evidente que o algoritmo guloso produz uma SCD da coleção dada. Resta provar que a SCD produzida é máxima. Para isso, é preciso entender as duas propriedades a seguir.

Propriedade da Escolha Gulosa:  Todo intervalo de término mínimo pertence a alguma SCD máxima.

Prova: Seja m um intervalo de término mínimo e X uma SCD máxima. Se m ∈ X, não há mais o que discutir. Suponha agora m ∉ X e seja q um intervalo de término mínimo em X. Observe que m é anterior a q e que todos os intervalos da subcoleção X são posteriores a q. Portanto, a coleção (X − { q}) ∪ {m} é disjunta, ou seja, é uma SCD. Ademais, essa nova coleção tem o mesmo tamanho que X, sendo portanto uma SCD máxima. Finalmente, observe que a nova coleção contém m, CQD.

Propriedade da Subestrutura Ótima:  Seja m um intervalo de término mínimo e X uma SCD máxima. Se m ∈ X então X − {m} é uma SCD máxima da coleção de todos os intervalos posterioresm.

Prova: Digamos que P é a coleção de todos os intervalos posteriores a m. É claro que a coleção X − {m} é disjunta. Como m tem término mínimo em X, a coleção X − {m} é uma subcoleção de P, ou seja, uma SCD de P. Resta mostrar que X − {m} é uma SCD máxima de P. Para isso, suponha que Y é uma SCD qualquer de P. Como Y ∪ {m} é disjunta, a maximalidade de X garante que Y ∪ {m}│ ≤ │X. Portanto Y│ ≤ │X − {m}│, o que prova que X − {m} é uma SCD máxima de P, CQD.

Essas duas propriedades explicam por que o algoritmo guloso esboçado acima está correto.

Exercícios 2

  1. Na prova da propriedade da escolha gulosa, mostre detalhadamente por que a coleção (X − { q}) ∪ {m} é uma SCD.
  2. Na prova da propriedade da subestrutura ótima, mostre detalhadamente por que X − {m} é uma SCD de P.

Versão recursiva do algoritmo guloso

Traduzir o algoritmo guloso em código exige um pouco de esforço. Para que o código seja eficiente, convém supor que os intervalos estão em ordem crescente de términos, ou seja, que

  b[p] ≤ b[p+1] ≤ ⋯ ≤ b[r] . (A)

Para escrever o algoritmo em estilo recursivo, será preciso adotar um intervalo fictício p − 1 com início e término nulos. O intervalo fictício será anterior a todos os demais intervalos pois todos têm inícios e términos positivos.

SCD-Max-Guloso (a, b, p, r)   pr
1 . a[p−1] := b[p−1] := 0
2 . devolva SCD-Max-r (a, b, p−1, r)

O subalgoritmo SCD-Max-r recebe uma coleção de intervalos (a[k .. r], b[k .. r]) em ordem crescente de términos e devolve uma SCD máxima da coleção de todos os intervalos que são posteriores ao intervalo k:

SCD-Max-r (a, b, k, r)   b crescente e kr
1 . m := k + 1
2 . enquanto mr e a[m] ≤ b[k]
3 .ooo m := m + 1
4 . se mr
5 .ooo X := SCD-Max-r (a, b, m, r)
6 .ooo devolva { m } ∪ X e pare
7 . devolva { }

No fim da linha 4, m é um intervalo de término mínimo dentre os que são posteriores a k. Na linha 6, m é escolhido para fazer parte da solução X. Na linha 7, o algoritmo devolve uma coleção vazia pois não encontrou intervalos posteriores a k.

Exemplo D.  A figura abaixo mostra a coleção de intervalos do exemplo C em ordem crescente de términos. Submeta essa coleção de intervalos ao algoritmo SCD-Max-Guloso. Mostre o resultado.
figs/mine/livrinho-intervals-noweights-2.png

Exercícios 3

  1. ★ Prove que o algoritmo SCD-Max-r faz o que promete fazer (ou seja, devolve uma SCD máxima da coleção de todos os intervalos que são posteriores ao intervalo k).
  2. ★ Supondo que o algoritmo SCD-Max-r faz o que promete fazer, prove que o algoritmo SCD-Max-Guloso está correto.
  3. ★ Qual o tamanho de uma instância do problema que SCD-Max-r resolve? Quanto tempo o algoritmo SCD-Max-r consome em função do tamanho da instância?
  4. Reescreva SCD-Max-r substituindo o conjunto X por seu vetor característico x[p .. r].

Versão iterativa do algoritmo guloso

A versão iterativa do algoritmo guloso é mais simples e mais interessante que a recursiva. Continuamos supondo que vale a condição (A), ou seja, que os intervalos são dados em ordem crescente de términos.

SCD-Max-Gula (a, b, p, r)   b crescente e pr
1 . X := { p }
2 . k := p
3 . para m := p+1 até r
4 .ooo se a[m] > b[k]
5 .oooooo X := X ∪ { m }
6 .oooooo k := m
7 . devolva X

No início da linha 4, k ∈ X e b[k] = maxi ∈ X b[i]. Portanto, todo intervalo m posteriork é disjunto de todos os intervalos em X. Na linha 5, m é o primeiro intervalo posterior a k. O algoritmo escolhe m para fazer parte da solução X sem saber o que virá depois. A escolha de m é definitiva e nunca será revista.

Quanto tempo o algoritmo SCD-Max-Gula consome? Vamos medir o tempo em relação ao número r − p + 1 de intervalos. Se denotarmos esse número por n, é fácil constatar que o algoritmo consome

Θ(n)

unidades de tempo para qualquer coleção de n intervalos. Mas isso não inclui o pré-processamento que coloca os intervalos em ordem crescente de término.

Exemplo E:  Considere a coleção de intervalos do exemplo B. A tabela abaixo registra a coleção em ordem crescente de términos. Execute o algoritmo SCD-Max-Gula com p = 1 e r = 8. O algoritmo percorre a tabela da esquerda para a direita. Os intervalos escolhidos para fazer parte da solução X (linha 5 do código) estão marcados com ☑ . Verifique se o algoritmo foi aplicado corretamente.

  1 2 3 4 5 6 7 8
a
b
6
15
9
15
7
16
18
24
1
26
23
28
25
30
30
34
 

Exemplo F:  A tabela abaixo registra uma coleção de 11 intervalos em ordem crescente de términos. Execute o algoritmo SCD-Max-Gula com p = 1 e r = 11. O algoritmo percorre a tabela da esquerda para a direita. Os intervalos escolhidos para fazer parte de X (linha 5 do código) estão marcados com ☑ .

  1 2 3 4 5 6 7 8 9 10 11
a
b
2
4
4
5
1
6
6
7
4
8
6
9
7
10
9
11
9
12
3
13
13
14
X              

Exercícios 4

  1. Escreva os invariantes do processo iterativo no algoritmo SCD-Max-Gula. (Em que ponto do código esses algoritmos valem?) Prove os invariantes. Use os invariantes para provar que o algoritmo está correto.
  2. ★ Prove que o algoritmo SCD-Max-Gula consome Θ(n) unidades de tempo, sendo n o número de intervalos.
  3. Para implementar o algoritmo SCD-Max-Gula de maneira eficiente, convém representar o conjunto X por seu vetor característico x[p .. r]. Escreva essa versão do algoritmo.
  4. A seguinte variante de SCD-Max-Gula está correta? O código supõe que b[p] ≤ … ≤ b[r]. Calcule o consumo de tempo do algoritmo.
    SCD-Max-Gula-2 (a, b, p, r)
    1 . X := { }
    2 . k := p
    3 . enquanto kr
    4 .ooo X := X ∪ { k }
    5 .ooo m := k + 1
    6 .ooo enquanto mr e a[m] ≤ b[k]
    7 .oooooo m := m + 1
    8 .ooo k := m
    9 . devolva X

Exercícios 5

  1. Ordem crescente de inícios.  Escreva uma variante do algoritmo SCD-Max-Gula supondo que os intervalos são dados em order crescente de inícios. Enuncie a versão apropriada da propriedade da escolha gulosa. Enuncie a versão apropriada da propriedade da subestrutura ótima.
  2. Suponha dada uma coleção C de intervalos. Seja (a′, b′) um intervalo em C que tem início máximo. Seja (a″, b″) um intervalo em C que tem término máximo. É verdade que (a′, b′) faz parte de toda SCD máxima de C?  É verdade que (a′, b′) faz parte de alguma SCD máxima de C?  É verdade que (a″, b″) faz parte de toda SCD máxima de C?  É verdade que (a″, b″) faz parte de alguma SCD máxima de C?
  3. ★ Digamos que a duração de um intervalo i é bi − ai. Coloque os intervalos em ordem crescente de duração. Escolha os intervalos gulosamente respeitando a ordem crescente de duração. Este algoritmo resolve o problema da coleção disjunta máxima de intervalos?
  4. Generalização: intervalos com pesos.  Considere a seguinte generalização do problema da coleção disjunta máxima de intervalos:  Dada uma coleção S de intervalos e um peso numérico pi ≥ 0 para cada intervalo i, encontrar uma SCD de S que tenha peso máximo. Escreva um algoritmo de programação dinâmica para o problema.
  5. Generalização: intervalos com sobpreposição limitada.  Seja L .. M um intervalo de números naturais. Diremos que esse conjunto é nosso universo. A cada elemento i do universo está associado um número natural ci que chamaremos capacidade. Dada uma coleção S de intervalos cujos inícios e términos pertencem ao universo, diremos que uma subcoleção X de S respeita as capacidades se, para cada i no universo, no máximo ci elementos de X contêm i. Problema: encontrar uma subcoleção máxima de S dentre as que respeitam as capacidades. Escreva um algoritmo para o problema.

Apêndice: identidade minimax

O problema da SCD máxima de intervalos goza de uma interessante propriedade minimax. (Trata-se de uma manifestação da dualidade em programação linear.)  Suponha dada uma coleção S de intervalos. Suponha que os inícios e términos de todos os elementos de S pertencem a um intervalo L .. M de números naturais que chamaremos universo. (No exemplo F acima, o universo é 1..14.)

Uma cobertura (= cover) de S é qualquer subconjunto Z do universo tal que todo intervalo em S contém pelo menos um elemento de Z. É evidente que

X│ ≤ │Z

para toda SCD X de S e toda cobertura Z de S. Portanto, se │X│ = │Z│ então X é uma SCD máxima (e Z é uma cobertura mínima). Assim, uma cobertura pode ser usada como prova da maximalidade de uma SCD máxima. (No exemplo F acima, o conjunto {4, 7, 11, 13} é uma cobertura. Esta cobertura prova que naquele exemplo não existe SCD com mais que quatro intervalos.)

O algoritmo SCD-Max-Gula pode ser modificado de modo a produzir uma SCD máxima X e uma cobertura Z de mesmo tamanho.

Exercícios 6

  1. Modifique o algoritmo SCD-Max-Gula para que ele devolva uma cobertura mínima e uma SCD máxima.