Course Schedule I e II
Rappresenti i prerequisiti dei corsi come un grafo orientato e usi l'ordinamento topologico per determinare se sia possibile completare tutti i corsi e in quale ordine.
Course Schedule I e II è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Panoramica del problema
Course Schedule I (LeetCode 207): dati n corsi e un elenco di coppie di prerequisites [a, b], dove "b deve essere seguito prima di a", determini se è possibile completare tutti i corsi. Course Schedule II (LeetCode 210): restituisca l'ordine effettivo in cui seguire i corsi oppure un array vuoto se non è possibile. Entrambi i problemi si riducono a un ordinamento topologico su un grafo orientato, in cui i prerequisiti sono rappresentati dagli archi.
Modellazione del grafo
Costruisca un grafo orientato: per ogni coppia di prerequisiti [a, b], aggiunga l'arco b → a, perché "b deve venire prima di a" significa che b porta ad a. Calcoli il grado entrante di ogni corso. Un corso con grado entrante pari a 0 non ha prerequisiti e può essere seguito immediatamente. Il problema è risolvibile se e solo se in questo grafo non esiste alcun ciclo, cioè alcuna dipendenza circolare.
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: soluzione con Kahn's
Utilizzi l'algoritmo di Kahn's. Se il numero di corsi elaborati è uguale a n, è possibile completare tutti i corsi. In caso contrario, una dipendenza circolare impedisce di completare il programma.
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: restituire l'ordine
Come per Course Schedule I, ma raccolga l'ordine dei corsi mentre li elabora. Restituisca l'ordine se include tutti i corsi; altrimenti restituisca una lista vuota.
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
Un'alternativa consiste nel rilevare i cicli con la DFS. I corsi hanno tre stati: non visitato (0), in elaborazione (1), completato (2). Se durante la DFS si raggiunge un corso in elaborazione, esiste un ciclo. Questo approccio è funzionalmente equivalente a Kahn's, ma utilizza una DFS ricorsiva.
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]])) # FalsePerché la direzione degli archi è importante
Un errore comune consiste nell'invertire la direzione degli archi: se il prerequisito è [a, b] e significa "b prima di a", aggiunga l'arco b → a, non a → b. La direzione dell'arco deve riflettere il flusso delle dipendenze: una freccia parte da ciò che deve essere completato per primo e punta verso ciò che dipende da esso. Con la direzione sbagliata, il rilevamento dei cicli e l'ordinamento risulteranno invertiti, producendo risultati errati nei problemi con più dipendenze.
Course Schedule III: variante greedy
Course Schedule III (LeetCode 630) è un problema diverso: i corsi hanno durate e scadenze e si desidera massimizzare il numero di corsi seguiti. Si risolve con un approccio greedy e un max-heap: si sceglie sempre per primo il corso con la scadenza più lontana; se l'aggiunta di un corso supera la sua scadenza, lo si sostituisce con il corso più lungo seguito finora, se quest'ultimo è più lungo. Si tratta di un problema greedy, non di ordinamento topologico: questo dimostra quanto sia importante leggere attentamente il testo del problema.
Gestire i nodi isolati
I corsi senza prerequisiti e senza corsi dipendenti sono nodi isolati: hanno grado entrante pari a 0 e nessun arco uscente. L'algoritmo di Kahn's li gestisce correttamente: vengono inseriti immediatamente nella coda ed elaborati. Si assicuri di inizializzare i gradi entranti per TUTTI i nodi da 0 a n-1, anche per quelli che non compaiono nell'elenco dei prerequisiti, altrimenti verranno ignorati.
# 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.Tempo di completamento parallelo dei corsi
Parallel Courses II: trovi il numero minimo di semestri necessari per seguire tutti i corsi quando è consentito seguire al massimo k corsi per semestre e devono essere rispettati i prerequisiti. Questo richiede l'elaborazione livello per livello di Kahn's con una programmazione dinamica su bitmask per il vincolo di selezione di k corsi: un problema significativamente più difficile, che combina l'ordinamento topologico con la programmazione dinamica su bitmask.
Strategia di comunicazione durante il colloquio
Quando affronta un problema del tipo Course Schedule durante un colloquio: (1) Identifichi immediatamente un problema di ordinamento topologico o di rilevamento dei cicli. (2) Modelli il grafo chiarendo la direzione degli archi. (3) Scelga Kahn's (BFS) per la semplicità oppure la DFS se la conosce meglio. (4) Gestisca esplicitamente il caso del ciclo. (5) Menzioni la complessità temporale O(V+E). Questo approccio strutturato dimostra capacità sistematiche di risoluzione dei problemi.
Test completo
Verifica di entrambe le soluzioni su una serie di input per confermarne la correttezza. L'approccio di Kahn's gestisce senza problemi i casi con più ordinamenti validi: per Course Schedule II, qualsiasi ordinamento topologico valido è accettabile come risposta.
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]])) # [] cycleVerifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: Course Schedule I e II utilizzano entrambi l'ordinamento topologico con l'arco b → a per il prerequisito [a, b], Course Schedule I verifica solo che len(order) == n, mentre Course Schedule II restituisce direttamente l'ordine e il rilevamento dei cicli basato sulla DFS con tre stati è un'alternativa valida all'approccio BFS di Kahn's. Ora esploreremo l'algoritmo di Kosaraju's per le componenti fortemente connesse.
Domande Frequenti
La lezione «Course Schedule I e II» è gratuita?
Sì — il testo completo di «Course Schedule I e II» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Course Schedule I e II»?
Rappresenti i prerequisiti dei corsi come un grafo orientato e usi l'ordinamento topologico per determinare se sia possibile completare tutti i corsi e in quale ordine. Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Course Schedule I e II»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Algoritmo di Kahn: ordinamento topologico BFS
- Ordinamento topologico DFS post-order
- Course Schedule I e II
- Componenti fortemente connesse con Kosaraju