0Pricing
DSA Interview Prep · Leçon

Planification de cours I et II

Modélisez les prérequis des cours par un graphe orienté et utilisez le tri topologique pour déterminer si tous les cours peuvent être terminés et dans quel ordre.

Planification de cours I et II est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.

Vue d’ensemble du problème

Planification des cours I (LeetCode 207) : étant donné n cours et une liste de paires de prerequisites [a, b] signifiant « b doit être suivi avant a », déterminez s’il est possible de terminer tous les cours. Planification des cours II (LeetCode 210) : renvoyez l’ordre réel dans lequel suivre les cours, ou un tableau vide si c’est impossible. Les deux problèmes se ramènent à un tri topologique sur un graphe orienté où les prérequis sont représentés par des arcs.

Modélisation du graphe

Construisez un graphe orienté : pour chaque paire de prérequis [a, b], appelez add pour créer l’arc b → a (« b doit précéder a », ce qui signifie que b mène à a). Calculez les degrés entrants de chaque cours. Un cours de degré entrant nul n’a aucun prérequis et peut être suivi immédiatement. Le problème est soluble si et seulement si aucun cycle n’existe dans ce graphe, c’est-à-dire aucune dépendance circulaire.

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))

Planification des cours I : solution de Kahn

Utilisez l’algorithme de Kahn. Si le nombre de cours traités est égal à n, tous les cours peuvent être terminés. Sinon, une dépendance circulaire empêche leur achèvement.

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]])) # False

Planification des cours II : renvoyer l’ordre

Même principe que pour Planification des cours I, mais recueillez l’ordre des cours au fur et à mesure de leur traitement. Renvoyez cet ordre si tous les cours y figurent ; sinon, renvoyez une liste vide.

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]]))

Planification des cours avec DFS

Une autre approche utilise DFS pour détecter les cycles. Les cours ont trois états : non visité (0), en cours (1), terminé (2). Si vous atteignez un cours en cours de traitement pendant DFS, un cycle existe. Cette approche est fonctionnellement équivalente à celle de Kahn, mais utilise un DFS récursif.

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]])) # False

Pourquoi le sens des arcs est important

Une erreur courante consiste à inverser le sens des arcs : si le prérequis est [a, b], ce qui signifie « b avant a », ajoutez l’arc b → a, et non a → b. Le sens de l’arc doit refléter le flux de dépendance : une flèche part de ce qui doit être fait en premier vers ce qui en dépend. Avec le mauvais sens, la détection des cycles et l’ordre seront inversés, ce qui donnera des résultats incorrects dans les problèmes comportant plusieurs dépendances.

Planification des cours III : variante gloutonne

Planification des cours III (LeetCode 630) est un problème différent : les cours ont des durées et des échéances, et vous voulez maximiser le nombre de cours suivis. Cela se résout par une approche gloutonne avec un tas max : prenez toujours d’abord le cours dont l’échéance est la plus tardive ; si l’ajout d’un cours dépasse son échéance, remplacez-le par le cours le plus long suivi jusqu’alors, s’il est plus long. Il s’agit d’un problème glouton, et non d’un problème de tri topologique — ce qui montre l’importance de lire attentivement les énoncés.

Gestion des sommets isolés

Les cours sans prérequis ni cours dépendants sont des sommets isolés : ils ont un degré entrant nul et aucun arc sortant. L’algorithme de Kahn les gère correctement : ils sont immédiatement ajoutés à la file d’attente et traités. Veillez à initialiser les degrés entrants de ALL les sommets de 0 à n-1, même ceux qui n’apparaissent pas dans la liste des prérequis, sinon ils seront oubliés.

# 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.

Durée d’achèvement des cours en parallèle

Cours en parallèle II : trouvez le nombre minimal de semestres nécessaires pour suivre tous les cours, avec au plus k cours par semestre et dans le respect des prérequis. Cela nécessite un traitement niveau par niveau de Kahn avec une DP par masque de bits pour la contrainte de sélection de k cours — un problème nettement plus difficile qui combine le tri topologique et la DP par masque de bits.

Stratégie de communication en entretien

Lorsque vous rencontrez un problème de type Planification des cours en entretien : (1) Identifiez immédiatement un problème de tri topologique et de détection de cycles. (2) Modélisez le graphe en clarifiant le sens des arcs. (3) Choisissez Kahn (BFS) pour sa simplicité, ou DFS si vous le maîtrisez mieux. (4) Traitez explicitement le cas d’un cycle. (5) Mentionnez la complexité temporelle O(V+E). Cette démarche structurée démontre des compétences systématiques de résolution de problèmes.

Test complet

Testez les deux solutions sur un éventail d’entrées afin d’en vérifier la validité. L’approche de Kahn gère élégamment les multiples ordres valides : tout ordre topologique valide est acceptable comme réponse pour Planification des cours 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]]))        # [] cycle

Vérification rapide

Testez votre compréhension des concepts de Structures de données et algorithmes & Préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris que les problèmes Planification des cours I et II utilisent tous deux le tri topologique, avec l’arc b → a pour le prérequis [a, b], que Planification des cours I vérifie simplement que la longueur de la liste des cours est égale à n, tandis que Planification des cours II renvoie l’ordre lui-même, et que la détection des cycles fondée sur DFS, avec trois états, constitue une alternative valide à l’approche BFS de Kahn. Nous allons ensuite explorer l’algorithme de Kosaraju pour les Strongly Connected Components.

Questions Fréquemment Posées

La leçon « Planification de cours I et II » est-elle gratuite ?

Oui — le texte complet de « Planification de cours I et II » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Planification de cours I et II » ?

Modélisez les prérequis des cours par un graphe orienté et utilisez le tri topologique pour déterminer si tous les cours peuvent être terminés et dans quel ordre. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?

Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.

Combien de temps prend la leçon « Planification de cours I et II » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?

Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Algorithme de Kahn : tri topologique par BFS
  2. Tri topologique par DFS en post-ordre
  3. Planification de cours I et II
  4. Composantes fortement connexes avec Kosaraju
← Retour à DSA Interview Prep