Course Schedule
Explore topological sorting applied to the course schedule problem to determine if all courses can be completed based on given prerequisites. Understand how to analyze prerequisite arrays, apply graph in-degree concepts, and implement solutions that return whether finishing all courses is possible. This lesson helps you organize tasks using topological sort and prepares you for similar real-world interview challenges.
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}