Course Schedule I y II
Modele los prerrequisitos de los cursos como un grafo dirigido y use ordenación topológica para determinar si pueden completarse todos los cursos y en qué orden.
Course Schedule I y II es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Descripción general del problema
Course Schedule I (LeetCode 207): dados n cursos y una lista de pares de prerequisites, donde [a, b] significa «b debe cursarse antes que a», determine si es posible terminar todos los cursos. Course Schedule II (LeetCode 210): devuelva el orden real en que deben cursarse los cursos, o un arreglo vacío si es imposible. Ambos problemas se reducen a aplicar un ordenamiento topológico a un grafo dirigido en el que los prerrequisitos son las aristas.
Modelado del grafo
Construya un grafo dirigido: para cada par de prerrequisitos [a, b], agregue la arista b → a («b debe aparecer antes que a» significa que b conduce a a). Calcule el grado de entrada de cada curso. Un curso con grado de entrada 0 no tiene prerrequisitos y puede cursarse de inmediato. El problema se puede resolver si y solo si no existe ningún ciclo en este grafo, es decir, ninguna dependencia circular.
from collections import defaultdict
def build_graph(n, prerequisites):
graph = defaultdict(list)
in_degree = [0] * n
for a, b in prerequisites: # b must come before a
graph[b].append(a)
in_degree[a] += 1
return graph, in_degree
graph, ind = build_graph(4, [[1,0],[2,0],[3,1],[3,2]])
print('In-degrees:', ind) # [0, 1, 1, 2]
print('Graph edges:', dict(graph))Course Schedule I: solución de Kahn
Utilice el algoritmo de Kahn. Si el número de cursos procesados es igual a n, se pueden terminar todos los cursos. De lo contrario, una dependencia circular impide completar el programa.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
course = queue.popleft()
count += 1
for nxt in graph[course]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # FalseCourse Schedule II: devolver el orden
Es igual que Course Schedule I, pero debe recopilar el orden de los cursos a medida que los procesa. Devuelva el orden si incluye todos los cursos; de lo contrario, devuelva una lista vacía.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
course = queue.popleft()
order.append(course)
for nxt in graph[course]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))Course Schedule con DFS
Una alternativa consiste en utilizar DFS para detectar ciclos. Los cursos tienen tres estados: sin visitar (0), en proceso (1) y terminados (2). Si durante el DFS se llega a un curso que está en proceso, existe un ciclo. Este enfoque es funcionalmente equivalente al de Kahn, pero utiliza un DFS recursivo.
from collections import defaultdict
def canFinish_dfs(numCourses, prerequisites):
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a)
# 0=unvisited, 1=in-progress, 2=done
state = [0] * numCourses
def has_cycle(course):
if state[course] == 1: return True # back edge
if state[course] == 2: return False # already cleared
state[course] = 1
for nxt in graph[course]:
if has_cycle(nxt):
return True
state[course] = 2
return False
return not any(has_cycle(i) for i in range(numCourses))
print(canFinish_dfs(2, [[1,0]])) # True
print(canFinish_dfs(2, [[1,0],[0,1]])) # FalsePor qué importa la dirección de las aristas
Un error común consiste en invertir la dirección de las aristas: si el prerrequisito es [a, b], lo que significa «b antes que a», agregue la arista b → a, no a → b. La dirección de la arista debe reflejar el flujo de las dependencias: una flecha apunta desde lo que debe hacerse primero hacia aquello que depende de ello. Con la dirección incorrecta, la detección de ciclos y el ordenamiento se invertirán, lo que producirá resultados incorrectos en problemas con múltiples dependencias.
Course Schedule III: variante codiciosa
Course Schedule III (LeetCode 630) es un problema diferente: los cursos tienen duraciones y fechas límite, y se desea maximizar el número de cursos realizados. Se resuelve de forma codiciosa con un montículo máximo: tome siempre primero el curso con la fecha límite más lejana; si al agregar un curso se supera su fecha límite, reemplácelo por el curso más largo realizado hasta ese momento, si este es más largo. Es un problema codicioso, no de ordenamiento topológico, lo que demuestra la importancia de leer atentamente los enunciados.
Gestión de nodos aislados
Los cursos sin prerrequisitos ni cursos dependientes son nodos aislados: tienen grado de entrada 0 y ninguna arista saliente. El algoritmo de Kahn los gestiona correctamente: se añaden a la cola y se procesan de inmediato. Asegúrese de inicializar los grados de entrada de TODOS los nodos de 0 a n-1, incluso los que no aparecen en la lista de prerrequisitos; de lo contrario, se omitirán.
# Example: 4 courses, but only courses 0 and 1 have a prerequisite relationship
# Courses 2 and 3 are isolated - they should appear in the output
from collections import deque, defaultdict
def findOrder_isolated(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses # initialise ALL nodes
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder_isolated(4, [[1,0]])) # [0,1,2,3] or [2,3,0,1] etc.Tiempo de finalización de cursos en paralelo
Parallel Courses II: encuentre el número mínimo de semestres necesarios para cursar todos los cursos cuando se permite cursar como máximo k cursos por semestre y deben respetarse los prerrequisitos. Esto requiere procesar los niveles uno por uno con el algoritmo de Kahn y utilizar DP con máscaras de bits para la restricción de selección de k cursos: un problema considerablemente más difícil que combina el ordenamiento topológico con DP mediante máscaras de bits.
Estrategia de comunicación en entrevistas
Al enfrentarse a un problema del tipo Course Schedule en una entrevista: (1) Identifíquelo inmediatamente como un problema de ordenamiento topológico o detección de ciclos. (2) Modele el grafo aclarando en qué dirección apuntan las aristas. (3) Elija Kahn (BFS) por su sencillez o DFS por familiaridad. (4) Gestione explícitamente el caso de ciclo. (5) Mencione la complejidad temporal O(V+E). Este enfoque estructurado demuestra habilidades sistemáticas para resolver problemas.
Prueba exhaustiva
Pruebe ambas soluciones con una variedad de entradas para verificar su corrección. El enfoque de Kahn gestiona correctamente varios órdenes válidos: cualquier orden topológico válido es aceptable como respuesta para Course Schedule II.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
c = queue.popleft(); order.append(c)
for nxt in graph[c]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0: queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(1, [])) # [0]
print(findOrder(2, [[0,1]])) # [1, 0]
print(findOrder(3, [[1,0],[2,1]])) # [0, 1, 2]
print(findOrder(3, [[1,0],[0,1]])) # [] cycleComprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió que: Course Schedule I y II utilizan el ordenamiento topológico con la arista b → a para el prerrequisito [a, b], Course Schedule I solo comprueba len(order) == n, mientras que Course Schedule II devuelve el orden y la detección de ciclos basada en DFS con tres estados es una alternativa válida al enfoque BFS de Kahn. A continuación exploraremos el algoritmo de Kosaraju para las componentes fuertemente conexas.
Aprende Coding Interview Prep con un tutor de IA — gratis
Escribe y ejecuta código real en tu navegador, obtén ayuda instantánea de un tutor de IA disponible 24/7 y continúa donde lo dejaste en la web o en la aplicación.
- Cursos
- 90
- Lecciones
- 360
Preguntas frecuentes
¿La lección «Course Schedule I y II» es gratis?
Sí — el texto completo de «Course Schedule I y II» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Course Schedule I y II»?
Modele los prerrequisitos de los cursos como un grafo dirigido y use ordenación topológica para determinar si pueden completarse todos los cursos y en qué orden. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Course Schedule I y II»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Algoritmo de Kahn: ordenación topológica con BFS
- Ordenación topológica con DFS en postorden
- Course Schedule I y II
- Componentes fuertemente conexas con Kosaraju