Course Schedule

Try to solve the Course Schedule problem.

We'll cover the following

Statement#

There are a total of num_courses courses you have to take. The courses are 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 [1,0][1, 0] indicates that to take course 11, you have to first take course 00.

Return TRUE if all of the courses can be finished. Otherwise, return FALSE.

Constraints:

  • 1≤1 \leq num_courses ≤1500\leq 1500
  • 0≤0 \leq prerequisites.length ≤1000\leq 1000
  • prerequisites[i].length =2= 2
  • 0≤0 \leq a[i], b[i] << num_courses
  • All the pairs prerequisites[i] are unique.

Examples#

Created with Fabric.js 3.6.6 Output Input Sample example 1 [[1, 0], [2, 1]] TRUE num_courses 3 prerequisites

1 of 3

Created with Fabric.js 3.6.6 Output Input Sample example 2 [[1, 0], [2, 1], [1, 2]] FALSE num_courses 3 prerequisites

2 of 3

Created with Fabric.js 3.6.6 Output Input Sample example 3 TRUE num_courses 5 prerequisites [[1, 0], [2, 1], [4, 3]] A valid order can be 0, 4, 1, 2, 3

3 of 3

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

1

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

A)

TRUE

B)

FALSE

Question 1 of 30 attempted

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.

Drag and drop the cards to rearrange them in the correct sequence.

Initialize a graph containing the key as the parent and the value as its child’s vertices.

Populate the in-degrees hash map.

Find all sources with 0 in-degrees.

For each source, append it to a sorted list, retrieve all of its children, and decrement the in-degrees of the respective child by 1.

Repeat the process until the source queue becomes empty.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
Course Schedule

Topological Sort: Introduction

Solution: Course Schedule