Solution: Tasks Scheduling

Blind 75

Problem Statement

There are ‘N’ tasks, labeled from ‘0’ to ‘N-1’. Each task can have some prerequisite tasks which need to be completed before it can be scheduled.

Given the number of tasks and a list of prerequisite pairs, find out if it is possible to schedule all the tasks.

Examples

Example 1:

Input: Tasks=6, Prerequisites=[2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3]
Output: true
Explanation: A possible scheduling of tasks is: [0 1 4 3 2 5]

Example 2:

Input: Tasks=3, Prerequisites=[0, 1], [1, 2]
Output: true
Explanation: To execute task '1', task '0' needs to finish first. Similarly, task '1' needs to finish before '2' can be scheduled. One possible scheduling of tasks is: [0, 1, 2]

Example 3:

Input: Tasks=3, Prerequisites=[0, 1], [1, 2], [2, 0]
Output: false
Explanation: The tasks have a cyclic dependency, therefore they cannot be scheduled.

Solution

This problem is asking us to find out if it is possible to find a topological ordering of the given tasks. The tasks are equivalent to the vertices and the prerequisites are the edges.

We can use a similar algorithm as described in Topological Sort to find the topological ordering of the tasks. If the ordering does not include all the tasks, we will conclude that some tasks have cyclic dependencies.

Step-by-step Algorithm

Initialize:
- Create an inDegree hashmap to keep count of incoming edges for every vertex (task).
- Create a graph hashmap to represent the adjacency list of the graph.
- Initialize both inDegree and graph for all tasks.
Build the Graph:
- For each prerequisite pair, update the adjacency list in graph and increment the inDegree for the child task.
Find All Sources:
- Find all vertices (tasks) with 0 in-degrees (no prerequisites) and add them to the sources queue.
Process Each Source:
- While there are tasks in the sources queue:
  - Remove a task from sources and add it to the sortedOrder.
  - For each child of the current task, decrement its inDegree by 1.
  - If a child's inDegree becomes 0, add it to the sources queue.
Check for Cyclic Dependencies:
- If the sortedOrder contains all tasks, it means there are no cyclic dependencies, and all tasks can be scheduled.
- If not, there is a cyclic dependency, and the tasks cannot be scheduled.

Algorithm Walkthrough

Given:

Tasks = 6
Prerequisites = [2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3]

Initialize:
- inDegree = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
- graph = {0: [], 1: [], 2: [], 3: [], 4: [], 5: []}
Build the Graph:
- For [2, 5]:
  - graph[2].append(5) → graph = {0: [], 1: [], 2: [5], 3: [], 4: [], 5: []}
  - inDegree[5]++ → inDegree = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 1}
- For [0, 5]:
  - graph[0].append(5) → graph = {0: [5], 1: [], 2: [5], 3: [], 4: [], 5: []}
  - inDegree[5]++ → inDegree = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 2}
- For [0, 4]:
  - graph[0].append(4) → graph = {0: [5, 4], 1: [], 2: [5], 3: [], 4: [], 5: []}
  - inDegree[4]++ → inDegree = {0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 2}
- For [1, 4]:
  - graph[1].append(4) → graph = {0: [5, 4], 1: [4], 2: [5], 3: [], 4: [], 5: []}
  - inDegree[4]++ → inDegree = {0: 0, 1: 0, 2: 0, 3: 0, 4: 2, 5: 2}
- For [3, 2]:
  - graph[3].append(2) → graph = {0: [5, 4], 1: [4], 2: [5], 3: [2], 4: [], 5: []}
  - inDegree[2]++ → inDegree = {0: 0, 1: 0, 2: 1, 3: 0, 4: 2, 5: 2}
- For [1, 3]:
  - graph[1].append(3) → graph = {0: [5, 4], 1: [4, 3], 2: [5], 3: [2], 4: [], 5: []}
  - inDegree[3]++ → inDegree = {0: 0, 1: 0, 2: 1, 3: 1, 4: 2, 5: 2}
Find All Sources:
- Sources are tasks with 0 in-degrees: sources = [0, 1]
Process Each Source:
- Process 0:
  - Remove 0 from sources → sources = [1]
  - Add 0 to sortedOrder → sortedOrder = [0]
  - For child 5 of 0, decrement inDegree[5] → inDegree[5] = 1
  - For child 4 of 0, decrement inDegree[4] → inDegree[4] = 1
- Process 1:
  - Remove 1 from sources → sources = []
  - Add 1 to sortedOrder → sortedOrder = [0, 1]
  - For child 4 of 1, decrement inDegree[4] → inDegree[4] = 0 → Add 4 to sources → sources = [4]
  - For child 3 of 1, decrement inDegree[3] → inDegree[3] = 0 → Add 3 to sources → sources = [4, 3]
- Process 4:
  - Remove 4 from sources → sources = [3]
  - Add 4 to sortedOrder → sortedOrder = [0, 1, 4]
- Process 3:
  - Remove 3 from sources → sources = []
  - Add 3 to sortedOrder → sortedOrder = [0, 1, 4, 3]
  - For child 2 of 3, decrement inDegree[2] → inDegree[2] = 0 → Add 2 to sources → sources = [2]
- Process 2:
  - Remove 2 from sources → sources = []
  - Add 2 to sortedOrder → sortedOrder = [0, 1, 4, 3, 2]
  - For child 5 of 2, decrement inDegree[5] → inDegree[5] = 0 → Add 5 to sources → sources = [5]
- Process 5:
  - Remove 5 from sources → sources = []
  - Add 5 to sortedOrder → sortedOrder = [0, 1, 4, 3, 2, 5]
Check for Cyclic Dependencies:
- sortedOrder = [0, 1, 4, 3, 2, 5] contains all tasks.
- All tasks can be scheduled without cyclic dependencies.

Code

Here is what our algorithm will look like:

Python3

Time Complexity

In step ‘d’, each task can become a source only once, and each edge (i.e., prerequisite) will be accessed and removed once. Therefore, the time complexity of the above algorithm will be $O(V+E)$ , where ‘V’ is the total number of tasks and ‘E’ is the total number of prerequisites.

Space Complexity

The space complexity will be $O(V+E)$ , since we are storing all of the prerequisites for each task in an adjacency list.