Course Schedule I i II
Modelować wymagania wstępne kursów jako graf skierowany i używać sortowania topologicznego do określenia, czy można ukończyć wszystkie kursy oraz w jakiej kolejności
Course Schedule I i II to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Omówienie problemu
Course Schedule I (LeetCode 207): mając n kursów i listę par prerequisites [a, b] oznaczających, że „kurs b musi zostać ukończony przed kursem a”, należy określić, czy można ukończyć wszystkie kursy. Course Schedule II (LeetCode 210): należy zwrócić rzeczywistą kolejność ukończenia kursów lub pustą tablicę, jeśli jest to niemożliwe. Oba problemy sprowadzają się do sortowania topologicznego grafu skierowanego, w którym wymagania wstępne są reprezentowane przez krawędzie.
Modelowanie grafu
Zbuduj graf skierowany: dla każdej pary wymagań wstępnych [a, b] dodaj krawędź b → a („b musi wystąpić przed a” oznacza, że b prowadzi do a). Oblicz stopień wejściowy każdego kursu. Kurs o stopniu wejściowym równym 0 nie ma wymagań wstępnych i można go ukończyć od razu. Problem ma rozwiązanie wtedy i tylko wtedy, gdy w tym grafie nie istnieje cykl (circular dependency).
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: rozwiązanie algorytmem Kahna
Użyj algorytmu Kahna. Jeśli liczba przetworzonych kursów jest równa n, można ukończyć wszystkie kursy. W przeciwnym razie cykliczna zależność uniemożliwia ukończenie wszystkich kursów.
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: zwracanie kolejności
Postępuj tak samo jak w Course Schedule I, ale zbieraj kolejność kursów podczas ich przetwarzania. Zwróć tę kolejność, jeśli obejmuje wszystkie kursy; w przeciwnym razie zwróć pustą listę.
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 z użyciem DFS
Alternatywą jest wykrywanie cykli za pomocą DFS. Kursy mają trzy stany: nieodwiedzony (0), w trakcie przetwarzania (1) i zakończony (2). Jeśli podczas DFS dotrzemy do kursu, który jest w trakcie przetwarzania, oznacza to istnienie cyklu. To podejście jest funkcjonalnie równoważne algorytmowi Kahna, ale wykorzystuje rekurencyjny 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]])) # FalseDlaczego kierunek krawędzi ma znaczenie
Częstym błędem jest odwrócenie kierunku krawędzi: jeśli wymaganie wstępne [a, b] oznacza „b przed a”, należy dodać krawędź b → a, a nie a → b. Kierunek krawędzi musi odzwierciedlać przepływ zależności: strzałka wskazuje od elementu, który musi zostać wykonany jako pierwszy, do elementu, który od niego zależy. Przy niepoprawnym kierunku wykrywanie cykli i ustalanie kolejności zostaną odwrócone, co prowadzi do błędnych wyników w zadaniach z wieloma zależnościami.
Course Schedule III: wariant zachłanny
Course Schedule III (LeetCode 630) to inny problem: kursy mają czas trwania i terminy, a celem jest zmaksymalizowanie liczby ukończonych kursów. Rozwiązuje się go zachłannie za pomocą kopca maksymalnego: zawsze najpierw wybieraj kurs z najpóźniejszym terminem; jeśli dodanie kursu spowoduje przekroczenie jego terminu, zastąp go najdłuższym dotychczas wybranym kursem (jeśli ten kurs trwa dłużej). Jest to problem zachłanny, a nie problem sortowania topologicznego — pokazuje to, jak ważne jest uważne czytanie treści zadań.
Obsługa izolowanych wierzchołków
Kursy bez wymagań wstępnych i bez kursów zależnych są izolowanymi wierzchołkami — mają stopień wejściowy 0 i nie mają krawędzi wychodzących. Algorytm Kahna poprawnie je obsługuje: są natychmiast dodawane do kolejki i przetwarzane. Należy pamiętać o zainicjalizowaniu stopni wejściowych dla WSZYSTKICH wierzchołków od 0 do n-1, także tych, które nie występują na liście wymagań wstępnych, ponieważ w przeciwnym razie zostaną pominięte.
# 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.Czas równoległego ukończenia kursów
Parallel Courses II: należy znaleźć minimalną liczbę semestrów potrzebną do ukończenia wszystkich kursów, gdy w każdym semestrze można ukończyć najwyżej k kursów, a wymagania wstępne muszą być respektowane. Wymaga to przetwarzania algorytmem Kahna poziom po poziomie oraz programowania dynamicznego z maską bitową do obsługi ograniczenia wyboru k kursów — jest to znacznie trudniejszy problem łączący sortowanie topologiczne z programowaniem dynamicznym z maską bitową.
Strategia komunikacji podczas rozmowy rekrutacyjnej
Podczas rozwiązywania zadania typu Course Schedule na rozmowie rekrutacyjnej: (1) Rozpoznaj je natychmiast jako problem sortowania topologicznego / wykrywania cykli. (2) Zamodeluj graf, ustalając kierunek krawędzi. (3) Wybierz algorytm Kahna (BFS) dla prostoty albo DFS, jeśli jest Państwu bardziej znany. (4) Obsłuż przypadek cyklu w sposób jawny. (5) Wspomnij o złożoności czasowej O(V+E). Takie uporządkowane podejście pokazuje systematyczne umiejętności rozwiązywania problemów.
Kompleksowy test
Przetestowanie obu rozwiązań na różnych danych wejściowych pozwala zweryfikować ich poprawność. Podejście algorytmem Kahna dobrze radzi sobie z wieloma poprawnymi kolejnościami — każda poprawna kolejność topologiczna jest akceptowalną odpowiedzią w 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]])) # [] cycleSzybki test
Sprawdź swoją wiedzę z zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: Course Schedule I i II wykorzystują sortowanie topologiczne z krawędzią b → a dla wymagania wstępnego [a, b], Course Schedule I sprawdza tylko, czy len(order) == n, natomiast Course Schedule II zwraca samą kolejność, a wykrywanie cykli za pomocą DFS i trzech stanów jest poprawną alternatywą dla podejścia BFS algorytmem Kahna. Następnie omówimy algorytm Kosaraju do znajdowania silnie spójnych składowych.
Często zadawane pytania
Czy lekcja „Course Schedule I i II” jest bezpłatna?
Tak — pełny tekst „Course Schedule I i II” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Course Schedule I i II”?
Modelować wymagania wstępne kursów jako graf skierowany i używać sortowania topologicznego do określenia, czy można ukończyć wszystkie kursy oraz w jakiej kolejności Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Course Schedule I i II”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Algorytm Kahna: sortowanie topologiczne za pomocą BFS
- Sortowanie topologiczne DFS w kolejności postorder
- Course Schedule I i II
- Silnie spójne składowe za pomocą algorytmu Kosaraju