Course Schedule

Introduction

Task scheduling problems are pretty prominent in the field of programming. In this article, we’ll learn how to solve one such problem named Course Schedule

These problems are frequently asked in Amazon, Microsoft and other product based companies.

Let’s understand the problem statement more precisely in the following section.

Problem Statement

You have been given ‘N’ courses and some courses may have prerequisites. Now consider a matrix ‘PREREQUISITES’ of size 'M' x 2 which means that you must complete course 'PREREQUISITES[i][1]' before the course 'PREREQUISITES[i][0]'.

Your task is to return the ordering of courses you should take to finish all courses.

Note: If there are multiple correct orders, print any one of them. If it is impossible to finish all the tasks, return an empty array. 

For example: 

INPUT : n = 2, 

prerequisites= [[1,0]]

OUTPUT: [0,1]

There are two tasks that need to be done and 1 needs 0 to be finished first. So we first complete 0 and then 1. 

INPUT : n = 4

prerequisites= [[1,0], [2,0], [3,1], [3,2]]

 

OUTPUT: [0,2,1,3]

 

There are four tasks, task 1 needs 0 to be completed first, task 2 needs 0 to be completed first, and task 3 needs tasks 1 and 2 to be completed first. Since 0 doesn’t need any pre-requisite task, 0 should be done first. Once 0 is done, 1 and 2 can be done in any order (Thus, there will be two different answers). Once 1 and 2 are done, we can surely do three.

 

Solution Approach 

The base of the solution is to think of this problem as a graph problem where the tasks are the vertices, and the prerequisites are the edges. If task u is a prerequisite of task v; we’ll add a directed edge from u to v. 

Now, you must have noticed that this problem reduces to just finding the correct topological ordering of the vertices of the above-described graph. For finding the topological order, we’ll use Kahn’s algorithm. You can learn more about this algorithm here.

Okk before we proceed, what do you think is it possible to find topological ordering in cyclic graphs?

Source: giphy

Consider the below cyclic graph and try to find the correct topological ordering.

Source: FSU computer science

Yes, you guessed it right. In cyclic graphs you can't decide which one to choose first.

Thus cyclic graphs never have any topological ordering, so if the graph contains a cycle, we’ll return an empty array in that case.

Stepwise Explanation

  • Input the number of tasks (vertices) and edges.
  • Store the edges in the adjacency vector and also store the indegree of all the tasks.
  • Whenever there is any pre-requisite of task u, increment its indegree by one because there will be an edge incoming towards it due to that prerequisite.
  • Create a queue for storing the vertices which don’t need any pre-requisite at the moment.
  • Initially, fill the queue with all the vertices whose in-degree is 0.
  • Run a loop from 0 to vertices-1 so that all the vertices are there in the topological ordering. Inside that loop, each time, check if the queue is empty. 
  • If the queue is empty at any iteration, it means that there is a cycle. So just return an empty array.
  • Otherwise, take the topmost element of the queue and complete that task. Since we’re finishing it, we’ll be storing it in our v vector, which keeps the topological ordering. 
  • Since we’re completing the current task, reduce the indegrees of all the tasks by one whose prerequisite was this current task. If, after doing so, there is any task whose indegree gets equal to 0, push it in the queue.
  • After doing total “vertices” iterations, return the vector v as it will contain the ordering. 
  • Finally, print the ordering. 

 

Consider the following visualisation for a better understanding:

Source: opengenus.org

 

Code

// Program to find order in which tasks needs to be done
#include <bits/stdc++.h>
using namespace std;

vector<int> kahn(int vertices,vector<vector<int>>&adj,vector<int>&indegree){  

    // Kahn's algo for finding topological ordering
    queue<int>q;  // queue for storing the tasks having indegree==0
    for(int i=0;i<vertices;i++){ 
        if(indegree[i]==0){  // first push all those elements into queue whose

            // indegree is 0
            q.push(i);
        }
    }
    vector<int>v;
    for(int i=0;i<vertices;i++){   // we'll be finishing all the tasks one by one,

         // therefore this for loop
        if(q.empty()){   // if at point we're not able to get any task which has

            // indegree = 0, return an empty array as there must have been a cycle then.
            return {};
        }
        int curr = q.front();  // get the front element of the queue as this will

         // be the task that we'll currently be doing 
        q.pop();               // pop from the queue
        v.push_back(curr);     // push the current task into the vector as its done
        for(auto x:adj[curr]){ // reduce the indegree of all the tasks which have

            // the current task as their pre-requisite by 1.
            indegree[x]--;
            if(indegree[x]==0){  // if after reducing the indegree becomes 0, push

                // it's in the queue.
                q.push(x);
            }
        }
    }
    return v;  // return the vector v containing the topological ordering
}

int main()
{
    int vertices, edges;  
    cin>>vertices>>edges;   // input the vertices and the edges
    vector<vector<int>>adj(vertices);  // adjacency vector for storing the edges.
    vector<int>indegree(vertices,0);   // vector for storing the indegree
    for(int i=0;i<edges;i++){
        int u,v;
        cin>>u>>v;  // input the pre-requisites (u needs v to be done first)
        adj[v].push_back(u);  // direct an edge from v to u.
        indegree[u]++;  // increase the indegree of u every time it has a prerequisite
    }
    vector<int>ans = kahn(vertices,adj,indegree);
    for(auto x:ans){  //print the topological ordering
        cout<<x<<" "
    }
    cout<<endl;
    return 0;
}

 

 

Input

4
3
1 0
2 1
3 2

 

Output

0 1 2 3

Complexities

Time complexity

O(V+E), where V is the number of vertices and E is the number of edges.

Reason: Because there is a for loop running V times and inside it, there is a loop running for edges, and the total number of edges is E.

Space complexity

O(V+E), where V is the number of vertices and E is the number of edges.

Reason: V for storing the vertices in the queue and E for storing the edges in the adjacency vector. 

Frequently asked questions

1. What is Kahn’s algorithm?

Answer: It is an algorithm used to find the topological ordering of vertices of a graph.

2. Is topological sorting BFS or DFS?

Answer: Topological sorting can be done using both BFS and DFS. However, Khan’s algorithm uses BFS. 

3. What is topological sorting?

Answer: Topological sorting is a linear ordering of vertices of a graph such that for every directed edge from u to v, u comes first in the ordering.

4. What is the time complexity of Kahn’s algorithm?

Answer: The time complexity of Kahn’s algorithm is O(V+E), where V is the number of vertices and E is the number of edges.

5. Where can I submit my “Course schedule” code?

Answer: You can submit your code on CodeStudio here and get it accepted right away.

6. Are there more Data Structures and Algorithms problems in CodeStudio?

Answer: Yes, CodeStudio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.

Key takeaways

In this article, we’ve discussed a problem that required topological ordering to be found out. One of the ways to find out the topological ordering was using Kahn’s algorithm. You can also find it out using DFS. For more details on this, refer to this article here. Also, there are many problems related to topological sorting like : 

Topological sortcourse schedule II and detect cycle in a directed graph

I would suggest you solve them to gain more confidence on this topic. These questions are asked during various coding contests as well as placements tests.

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

 

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think