Queremos obter um algoritmo por divisão e conquista que compute o skyline de n prédios. Um prédio Pi é representado pela tripla ( Ei, Ai, Di ), onde Ei e Di denotam as coordenadas x mais à esquerda e mais à direita de Pi, respectivamente, e Ai denota a altura de Pi. O skyline de n prédios é uma lista de coordenadas x e alturas que conectam os prédios, ordenados da esquerda para direita. (note que esta lista tem tamanho no máximo 4 n ).
Exemplo: O skyline dos prédios (3, 13, 9),(1, 11, 5),(1 2, 7,16),(1 4, 3, 2 5), (1 9, 18, 2 2),(2, 6, 7),(2 3, 13, 2 9) e (2 3, 4, 2 8) é (1, 11, 3, 13, 9, 0, 1 2, 7, 1 6, 3, 1 9, 18, 2 2, 3, 2 3, 13, 2 9, 0)
(a) Sabendo que o tamanho do skyline é o total de elementos (coordenadas e alturas) existentes na sua lista (No exemplo apresentado, o tamanho da skyline é 18), descreva um algoritmo que combina o skyline A de tamanho n1 e o skyline B de tamanho n2 no skyline de tamanaho O(n1+n2). Seu algoritmo deve ter complexidade O(n1+n2).
Resposta:
Criamos uma lista L, inicialmente vazia, e fazemos uma varredura em A e B da seguinte forma: obtemos o menor dentre os E1

Passo 1

O enunciado pede um sub‐algoritmo de mesclagem (merge) para dois skylines A e B de tamanhos n₁ e n₂, devolvendo o skyline combinado em O(n₁+n₂). O conteúdo é algoritmo de divisão e conquista aplicando uma varredura semelhante ao merge do mergesort, mantendo alturas correntes.

Passo 2

Representamos cada skyline como uma lista de pares ordenados (x, h). Definimos índices i=1 para A e j=1 para B, duas variáveis de altura corrente h₁=0 e h₂=0, e uma variável últimaAltura=0. O resultado é acumulado numa lista L vazia.

Passo 3

Enquanto i ≤ n₁ e j ≤ n₂, comparamos A[i].x e B[j].x. Se A[i].x < B[j].x atualizamos x ← A[i].x, h₁ ← A[i].h e incrementamos i. Se B[j].x < A[i].x fazemos x ← B[j].x, h₂ ← B[j].h e j ← j+1. Se empatarem em x, fazemos x ← A[i].x, h₁ ← A[i].h, h₂ ← B[j].h e incrementamos i e j.
Após escolher x, calculamos h ← max(h₁,h₂). Se h ≠ últimaAltura então adicionamos (x,h) em L e atualizamos últimaAltura ← h.

Passo 4

Quando um dos skylines terminar, processamos o restante do outro de forma análoga: para cada par (x,h) no skyline remanescente atualizamos h₁ ou h₂, recalculamos h ← max(h₁,h₂) e, se h ≠ últimaAltura, incluímos (x,h) em L.

Passo 5

Como cada ponto de A e de B é visitado exatamente uma vez, a complexidade do algoritmo é O(n₁+n₂).

Resposta

Segue o pseudocódigo em estilo textual:
– Inicializar L ← lista vazia, i ← 1, j ← 1, h₁ ← 0, h₂ ← 0, últimaAltura ← 0.
– Enquanto i ≤ n₁ e j ≤ n₂:
• Se A[i].x < B[j].x então x ← A[i].x, h₁ ← A[i].h, i ← i+1;
• Senão se B[j].x < A[i].x então x ← B[j].x, h₂ ← B[j].h, j ← j+1;
• Senão (mesmo x) x ← A[i].x, h₁ ← A[i].h, h₂ ← B[j].h, i ← i+1, j ← j+1;
• h ← max(h₁,h₂);
• Se h ≠ últimaAltura então inserir (x,h) em L e atualizar últimaAltura ← h.
– Processar o restante de A (se i ≤ n₁) e depois o restante de B (se j ≤ n₂) do mesmo modo: para cada (x,h) atualizar h₁ ou h₂, recalcular h ← max(h₁,h₂) e inserir (x,h) em L se h ≠ últimaAltura.
O resultado L é o skyline combinado e o algoritmo roda em O(n₁+n₂).

Exercícios relacionados