Course Schedule
Explore how to apply topological sort to solve course scheduling problems by analyzing prerequisite relationships. Understand the logic behind ordering courses to verify if all can be finished, and practice implementing solutions using this essential graph pattern.
We'll cover the following...
Statement
You are given an integer, num_courses, representing the total number of courses you need to complete, labeled from 0 to num_courses - 1.
You are also given a prerequisites array, where prerequisites[i] = [a[i], b[i]] indicates that you must take course b[i] first if you want to take the course a[i]. For example, the pair indicates that to take course , you have to first take course .
Return TRUE if all of the courses can be finished. Otherwise, return FALSE.
Constraints:
-
num_courses -
prerequisites.length prerequisites[i].length-
a[i],b[i]num_courses - All the pairs
prerequisites[i]are unique.
Examples
Understand the problem
Let’s take a moment to make sure you've correctly understood the problem. The quiz below helps you check if you're solving the correct problem:
Course Schedule
What is the output if the following prerequisites and number of courses are given as input?
prerequisites = [[1, 0], [1, 2], [3, 1], [4, 1], [1, 4], [5, 1]]
num_courses = 6
TRUE
FALSE
Note: The in-degree is the number of edges coming into a vertex in a directed graph.
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground.
def can_finish(num_courses, prerequisites):# Replace this placeholder return statement with your codereturn False