Understanding the Problem
We are given a number of courses, and a list of prerequisite pairs. Each pair [a, b]
means you must complete course b
before course a
. Our task is to determine if it’s possible to finish all courses, and if yes, return one possible order in which to take them.
This is a classic problem of dependency resolution and can be modeled as a directed graph where each course is a node, and each prerequisite is a directed edge. If the graph contains a cycle, then it is impossible to finish all courses. Otherwise, we can generate a valid course order using topological sorting.
Step-by-Step Solution with Example
Step 1: Represent the Problem as a Graph
We treat each course as a node. If course b
is a prerequisite for course a
, we draw a directed edge from b
to a
.
Example:
Let’s say numCourses = 4
and prerequisites = [[1,0],[2,0],[3,1],[3,2]]
.
This means:
- Take course 0 before 1
- Take course 0 before 2
- Take course 1 before 3
- Take course 2 before 3
So, the graph looks like:
0 → 1 → 3
↑
→ 2 ———┘
Step 2: Initialize In-Degree Array and Adjacency List
The in-degree of a node is the number of prerequisites it has. We create:
- An adjacency list to store which courses depend on each course.
- An in-degree array to count prerequisites for each course.
Step 3: Enqueue Courses with In-Degree 0
Courses with no prerequisites (in-degree 0) can be taken immediately. We add them to a queue.
In our example, only course 0 has in-degree 0 initially, so we enqueue it.
Step 4: Process the Queue
While the queue is not empty:
- Remove a course from the queue and add it to the result list.
- For each course that depends on it, reduce its in-degree by 1.
- If any course’s in-degree becomes 0, enqueue it.
For our example:
- Start with [0]
- Process 0 → add [1, 2] to queue → result: [0]
- Process 1 → reduce in-degree of 3 → result: [0, 1]
- Process 2 → reduce in-degree of 3 → result: [0, 1, 2]
- Now 3 has in-degree 0 → enqueue → result: [0, 1, 2, 3]
Step 5: Check if All Courses Are Taken
If the result list contains all courses, we return it. If not, it means there’s a cycle and we return an empty array.
Edge Cases
- Cycle in prerequisites: Example:
[[1,0],[0,1]]
. This creates a loop: 0 → 1 → 0. It’s impossible to finish all courses.
- No prerequisites: All courses are independent. Any order is valid.
- Single course: Always possible to finish it.
- Multiple valid orders: For acyclic graphs, many topological sorts are possible.
Finally
This problem teaches us how to model real-world scheduling problems using graphs. Topological sorting is the key idea, and cycle detection helps us rule out impossible scenarios. By translating the prerequisites into a graph and using in-degree tracking, we can determine if all tasks (courses) can be completed, and in what order.
Comments
Loading comments...