Course Schedule / Job Scheduling

Get started

🙏
জয় শ্রী রাম
🕉

Prerequisites:

Problem #1: Feasibility of Job Scheduling or Course Scheduling

Problem Statement:

Flavor #1

There are a total of N jobs you have to get done , labeled from 0 to numCourses-1.
Some jobs may have dependency on other job(s), for example to do job 0 you have to first get job 1 done, which is expressed as a pair: [0,1].
Given the total number of jobs and a list of dependencies, is it possible for you to finish all jobs?
Example 1:
Input: N = 2, dependencies = [[1,0]] Output: true Example 2: Input: N = 2, dependencies = [[1,0],[0,1]] Output: false

Flavor #2

There are a total of N courses you have to take , labeled from 0 to numCourses-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]. For
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. Example 2: Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Solutions:

NOTE: All the solutions below have O(V + E) time complexity, where V = total number of vertices in a given graph and E = total number of edges in a given graph, since we are visiting all edges and all vertices. So if there are N given jobs or courses the time complexity will be O(N²) in worst case since in worst case the dependency graph will be dense, i.e, every job . course will have dependency on all other jobs/courses.

Using Concept of Strongly Connected Components and Tarjan's Algorithm:

If there is a circular dependency (cycles) among two or more jobs/courses then the scheduling is not possible. Every vertex in a directed graph for strongly connected component with itself. So a Strongly Connected Component (SCC) is not a cycle only when the SCC has only one vertex. Any SCC with more than one vertices is a cycle. In short the scheduling is feasible only if the given directed graph is actually a DAG or Directed ACYCLIC Graph. So we will go on finding SCCs in the given dependency graph and at any point of time if we find an SCC with more than one vertex, we will return false.

Java Code:

Python Code:

Using Concept of Cycle:

The scheduling is possible only when the given directed graph is a DAG or directed ACYCLIC graph. If the given dependency graph has any circular dependency (cycles) among two or more vertices, the scheduling is not possible. So the problem boils down to finding cycle(s) in the given directed graph.
Please see the chapters: 5 Ways to Find Cycles and Cycle Detection Using DFS.

Java Code:

Python Code:

Using Concept of Topological Sort:

If there is a topological sort of all the given courses or jobs possible, then there is no cycle and the job/course scheduling is possible.
Please see the chapter: Topological Sort .

Java Code:

Python Code:

Problem #2: Order of scheduled Jobs or Courses

Problem Statement:

There are a total of n courses you have to take labelled from 0 to n - 1.
Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.
Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.
If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
Example 2:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Solutions:

Solution based on finding SCCs using Tarjan's Algorithm:

Please visit Strongly Connected Components (SCC) for detailed discussion. We have seen there that while there is nothing special about the order of the nodes within each strongly connected component, one useful property of the Tarjan's algorithm is that no strongly connected component will be identified before any of its successors. Therefore, the order in which the strongly connected components are identified constitutes a reverse topological sort of the DAG formed by the strongly connected components.
This observation becomes quite intuitively if you recall the Topological Sort using DFS. There too we get the nodes in the opposite order of the topological order after the Depth First Search is done. Same thing here too since Tarjan's Algorithm is based on DFS.
So for this specific problem: If there is no cycle then all the SCC will consist of only one node. So basically getting the reverse topological order of SCC will be same as getting the nodes in reverse topological order.

Java Code:

Python Code:

Solution using Topological Sort:

All we need to do is return the Topological Sort of the given jobs or courses, if and only if, there is no circular dependency (cycle).

Java Code:

Python Code:

Don't forget to take a look at other interesting Graph Problems:

Instructor:

Abhishek Dey

Senior SDE | Chief Architect

AWS | Microsoft | University of Florida

View LinkedIn profile