# 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:

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. |

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 // Kahn's algo for finding topological ordering // indegree is 0 // therefore this for loop // indegree = 0, return an empty array as there must have been a cycle then. // be the task that we'll currently be doing // the current task as their pre-requisite by 1. // it's in the queue. |

**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 sort__, __course 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!

Comments

## No comments yet

## Be the first to share what you think