Course Schedule
Explore how to use topological sorting to solve course scheduling problems. Understand how to check if you can complete all courses given prerequisites, and practice implementing a solution to this common interview pattern.
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]]
numCourses = 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.
import Queue from './Queue.js'export function canFinish(numCourses, prerequisites) {// Replace this placeholder return statement with your codereturn false}