Queremos obter um algoritmo por divisão e conquista que compute o skyline de
prédios. Um prédio
é representado pela tripla (
), onde
e
denotam as coordenadas
mais à esquerda e mais à direita de
, respectivamente, e
denota a altura de
. O skyline de
prédios é uma lista de coordenadas
e alturas que conectam os prédios, ordenados da esquerda para direita. (note que esta lista tem tamanho no máximo
).
Exemplo: O skyline dos prédios
,
e
é
(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
de tamanho
e o skyline
de tamanho
no skyline de tamanaho
. Seu algoritmo deve ter complexidade
.
Resposta:
Criamos uma lista
, inicialmente vazia, e fazemos uma varredura em
e
da seguinte forma: obtemos o menor dentre os
Exemplo: O skyline dos prédios
(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
Resposta:
Criamos uma lista
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.
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.
• 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₂).