Course Schedule I og II
Modellér kursusforudsætninger som en rettet graf, og brug topologisk sortering til at afgøre, om alle kurser kan gennemføres, og i hvilken rækkefølge.
Course Schedule I og II er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Problemoversigt
Course Schedule I (LeetCode 207): Givet n kurser og en liste med par af prerequisites i form af [a, b], hvor »b skal tages før a«, skal du afgøre, om du kan gennemføre alle kurser. Course Schedule II (LeetCode 210): Returnér den faktiske rækkefølge, kurserne skal tages i, eller et tomt array, hvis det ikke er muligt. Begge opgaver kan reduceres til topologisk sortering på en rettet graf, hvor forudsætningerne udgør kanterne.
Modellering af grafen
Opbyg en rettet graf: For hvert par af forudsætninger [a, b] skal du tilføje kanten b → a (»b skal komme før a« betyder, at b fører til a). Beregn indgraderne for hvert kursus. Et kursus med indgrad 0 har ingen forudsætninger og kan tages med det samme. Opgaven kan løses, hvis og kun hvis der ikke findes nogen cyklus i grafen (ingen cirkulær afhængighed).
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: Kahns løsning
Brug Kahns algoritme. Hvis antallet af behandlede kurser er lig med n, kan alle kurser gennemføres. Ellers forhindrer en cirkulær afhængighed, at de kan gennemføres.
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: Returnér rækkefølgen
Det fungerer på samme måde som i Course Schedule I, men du skal indsamle kursernes rækkefølge, mens du behandler dem. Returnér rækkefølgen, hvis alle kurser er med, ellers returneres en tom liste.
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 med DFS
Et alternativ er at bruge DFS til cyklusdetektion. Kurser har tre tilstande: ikke besøgt (0), under behandling (1) og færdig (2). Hvis vi under DFS når frem til et kursus, der er under behandling, findes der en cyklus. Denne tilgang er funktionelt ækvivalent med Kahn, men bruger rekursiv DFS.
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]])) # FalseHvorfor kantenes retning er vigtig
En almindelig fejl er at vende kantenes retning forkert: Hvis forudsætningen er [a, b] og betyder »b før a«, skal du tilføje kanten b → a og ikke a → b. Kantenes retning skal afspejle afhængighedsflowet: En pil peger fra det, der skal udføres først, til det, der afhænger af det. Med den forkerte retning bliver cyklusdetektionen og rækkefølgen vendt om, hvilket giver forkerte resultater i opgaver med flere afhængigheder.
Course Schedule III: Grådig variant
Course Schedule III (LeetCode 630) er en anden opgave: Kurser har varigheder og tidsfrister, og du vil maksimere antallet af kurser, du tager. Den løses grådigt med en max-heap: Tag altid først kurset med den seneste tidsfrist; hvis tilføjelsen af et kursus overskrider dets tidsfrist, skal du erstatte det med det længste kursus, du hidtil har taget (hvis dette kursus er længere). Dette er en grådig løsning og ikke en opgave om topologisk sortering — det viser, hvor vigtigt det er at læse opgavebeskrivelser grundigt.
Håndtering af isolerede knuder
Kurser uden forudsætninger og uden afhængige kurser er isolerede knuder — de har indgrad 0 og ingen udgående kanter. Kahns algoritme håndterer dem korrekt: De sættes straks i kø og behandles. Sørg for at initialisere indgraderne for ALLE knuder fra 0 til n-1, også dem der ikke forekommer på listen over forudsætninger, ellers bliver de overset.
# 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.Tid til at gennemføre kurser parallelt
Parallel Courses II: Find det mindste antal semestre, der kræves for at tage alle kurser, når der højst må tages k kurser pr. semester, og forudsætningerne skal overholdes. Det kræver niveauvis behandling med Kahn kombineret med bitmask-DP for begrænsningen på valget af k kurser — en betydeligt sværere opgave, der kombinerer topologisk sortering med bitmask-DP.
Kommunikationsstrategi til interviewet
Når du møder en opgave af typen Course Schedule i et interview: (1) Identificér den straks som et problem om topologisk sortering og cyklusdetektion. (2) Modellér grafen ved at afklare, hvilken retning kanterne peger i. (3) Vælg Kahn (BFS) for enkelhed eller DFS, hvis du er fortrolig med den. (4) Håndtér cyklustilfældet eksplicit. (5) Nævn tidskompleksiteten O(V+E). Denne strukturerede tilgang viser systematiske problemløsningsevner.
Omfattende test
Afprøv begge løsninger på en række input for at kontrollere korrektheden. Kahn-tilgangen håndterer flere gyldige rækkefølger på en robust måde — enhver gyldig topologisk rækkefølge er acceptabel som svar i 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]])) # [] cycleHurtigt tjek
Afprøv din forståelse af begreberne fra denne lektion i Data Structures & Algorithms — Coding Interview Prep.
Opsummering af lektionen
I denne lektion har du lært: Course Schedule I og II bruger begge topologisk sortering med kanten b → a for forudsætningen [a, b], Course Schedule I tjekker blot len(order) == n, mens Course Schedule II returnerer selve rækkefølgen, og DFS-baseret cyklusdetektion med tre tilstande er et gyldigt alternativ til Kahns BFS-tilgang. Næste gang ser vi på Kosarajus algoritme til stærkt sammenhængende komponenter.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Course Schedule I og II” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Course Schedule I og II”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Course Schedule I og II”?
Modellér kursusforudsætninger som en rettet graf, og brug topologisk sortering til at afgøre, om alle kurser kan gennemføres, og i hvilken rækkefølge. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Course Schedule I og II”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Kahns algoritme: Topologisk sortering med BFS
- Topologisk sortering med DFS-efterorden
- Course Schedule I og II
- Stærkt sammenhængende komponenter med Kosaraju