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 Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-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 Forberedelse til kodeinterviews 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
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Course Schedule I og II” gratis?
Ja — hele teksten til “Course Schedule I og II” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-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 Forberedelse til kodeinterviews 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å Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews 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 Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-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