Course Schedule
Explore the topological sort technique to determine if all courses can be completed given prerequisite constraints. This lesson guides you through understanding task dependencies and implementing a solution to commonly encountered course scheduling problems in coding interviews.
We'll cover the following...
Statement
You are given an integer, numCourses, representing the total number of courses you need to complete, labeled from 0 to numCourses - 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:
-
numCourses -
prerequisites.length prerequisites[i].length-
a[i],b[i]numCourses - 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:
bool CanFinish(int numCourses, vector<vector<int>> preRequisites) {// Replace this placeholder return statement with your codereturn false;}