Ordenar los pasos del build
La misión
Problema
Un build tiene n pasos numerados de 0 a n - 1, y deps lista pares [a, b] que significan que el paso a debe terminar antes de que empiece el paso b. Devuelve un orden que ejecute cada paso después de todos sus prerrequisitos. Si hay varios órdenes válidos, se acepta cualquiera. Si las dependencias forman un ciclo y no existe ningún orden, devuelve una lista vacía.
Ejemplos
Input: n = 4, deps = [[0, 1], [0, 2], [1, 3], [2, 3]]
Output: [0, 1, 2, 3]
Por qué: 0 va primero, 1 y 2 solo necesitan a 0, y 3 espera a ambos (ejecutar 2 antes que 1 también es válido)
Input: n = 3, deps = [[0, 1], [1, 2], [2, 0]]
Output: []
Por qué: cada paso espera a otro paso en un ciclo, así que ninguno puede empezar nunca
Input: n = 3, deps = []
Output: [0, 1, 2]
Por qué: caso límite: sin dependencias, cualquier orden funciona
Pistas
0 / 3
Un paso puede ejecutarse en cuanto no le queda pendiente nada de lo que depende. ¿Qué pasos pueden ejecutarse justo al principio?
Cuenta, para cada paso, cuántos prerrequisitos sigue esperando. Ejecutar un paso baja ese conteo en cada paso que depende de él, y un conteo que llega a cero significa que ese paso está listo.
Empieza una cola con todos los pasos cuyo conteo es cero. Saca un paso, agrégalo al orden y decrementa los conteos de los pasos que van después de él, encolando los que lleguen a cero. Si el orden termina siendo más corto que n, un ciclo bloqueó el resto, así que devuelve una lista vacía.
- Tiempo objetivo
- O(n + m)
- Espacio objetivo
- O(n + m)
Restricciones
- steps are numbered 0 to n - 1
- any valid order is accepted
Solución
Este es el ordenamiento topológico de Kahn. El grado de entrada de un paso es la cantidad de prerrequisitos que sigue esperando, así que los pasos con grado de entrada cero son exactamente los que pueden ejecutarse ahora. Ejecutar uno elimina sus aristas salientes, lo que puede liberar más pasos, y una cola (queue) los va agregando al orden a medida que quedan listos. Los pasos que están en un ciclo nunca llegan a grado de entrada cero, así que nunca entran al orden, y un orden corto es la señal de que no existe ningún orden válido. Cada paso y cada dependencia se procesan una vez, así que el tiempo es O(n + m) para m dependencias, y el espacio es 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]¿Lo que te frena es la idea y no el código? Ordenamiento topológico lo explica.