Ordenar as etapas do build
A missão
Problema
Um build tem n etapas numeradas de 0 a n - 1, e deps lista pares [a, b] que significam que a etapa a precisa terminar antes que a etapa b comece. Retorne uma ordem que execute cada etapa depois de todos os seus pré-requisitos. Se várias ordens forem válidas, qualquer uma delas é aceita. Se as dependências formarem um ciclo, de modo que nenhuma ordem exista, retorne uma lista vazia.
Exemplos
Input: n = 4, deps = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: [0, 1, 2, 3]
Por quê: 0 vai primeiro, 1 e 2 só precisam de 0, e 3 espera pelos dois (executar 2 antes de 1 também é válido)
Input: n = 3, deps = [[0, 1], [1, 2], [2, 0]]
Output: []
Por quê: cada etapa espera por outra em um ciclo, então nenhuma consegue começar
Input: n = 3, deps = []
Output: [0, 1, 2]
Por quê: edge case: sem dependências, qualquer ordem funciona
Dicas
0 / 3
Uma etapa pode rodar assim que nada de que ela depende estiver pendente. Quais etapas podem rodar logo no início?
Conte, para cada etapa, quantos pré-requisitos ela ainda espera. Executar uma etapa diminui essa contagem para cada etapa que depende dela, e uma contagem que chega a zero significa que aquela etapa está pronta.
Comece uma fila com todas as etapas cuja contagem é zero. Retire uma etapa da fila, adicione-a à ordem e decremente as contagens das etapas que vêm depois dela, enfileirando as que chegarem a zero. Se a ordem final ficar menor que n, um ciclo bloqueou o resto; então retorne uma lista vazia.
- Tempo-alvo
- O(n + m)
- Espaço-alvo
- O(n + m)
Restrições
- steps are numbered 0 to n - 1
- any valid order is accepted
Solução
Esta é a ordenação topológica pelo algoritmo de Kahn. O grau de entrada de uma etapa é o número de pré-requisitos que ela ainda espera, então as etapas com grau de entrada zero são exatamente as que podem rodar agora. Executar uma delas remove suas arestas de saída, o que pode liberar mais etapas, e uma fila as coloca na ordem conforme ficam prontas. Etapas em um ciclo nunca chegam a grau de entrada zero, então nunca entram na ordem, e uma ordem curta é o sinal de que não existe ordem válida. Cada etapa e cada dependência são tratadas uma vez, então o tempo é O(n + m) para m dependências, e o espaço é O(n + m).
from collections import deque
def build_order(n, deps):
after = [[] for _ in range(n)]
waiting = [0] * n # in-degree: prerequisites still pending
for a, b in deps:
after[a].append(b)
waiting[b] += 1
ready = deque(i for i in range(n) if waiting[i] == 0)
order = []
while ready:
step = ready.popleft()
order.append(step)
for nxt in after[step]:
waiting[nxt] -= 1
if waiting[nxt] == 0: # its last prerequisite just ran
ready.append(nxt)
return order if len(order) == n else [] # short order: a loop blocked the rest
print(build_order(4, [[0, 1], [0, 2], [1, 3], [2, 3]])) # -> [0, 1, 2, 3]
print(build_order(3, [[0, 1], [1, 2], [2, 0]])) # -> []
print(build_order(3, [])) # -> [0, 1, 2]Travou na ideia, e não no código? Ordenação topológica explica isso.