Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Tasks Scheduling Order
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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, write a method to find the ordering of tasks we should pick to finish all tasks.

Examples

Example 1:

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

Example 2:

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

Example 3:

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

Solution

This problem is similar to Tasks Scheduling, the only difference being that we need to find the best ordering of tasks so that it is possible to schedule them all.

Step-by-step Algorithm

  1. Initialize the Graph:

    • Create a HashMap inDegree to count the incoming edges for every vertex.
    • Create a HashMap graph to represent the adjacency list of the graph.
  2. Build the Graph:

    • For each task, set the initial in-degree to 0 and create an empty adjacency list.
    • For each prerequisite pair [parent, child]:
      • Add child to the adjacency list of parent.
      • Increment the in-degree of child by 1.
  3. Find All Sources:

    • Initialize a queue sources and add all vertices with 0 in-degrees.
  4. Sort Tasks:

    • While sources is not empty:
      • Remove a source from the queue, add it to sortedOrder.
      • For each child of this source:
        • Decrement the child's in-degree by 1.
        • If the child's in-degree becomes 0, add it to the sources queue.
  5. Check for Cyclic Dependencies:

    • If the size of sortedOrder is not equal to the number of tasks, return an empty list (indicating a cycle).
    • Otherwise, return sortedOrder.

Algorithm Walkthrough

Given:

  • Tasks = 6
  • Prerequisites = [2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3]
  1. Initialize:

    • inDegree = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
    • graph = {0: [], 1: [], 2: [], 3: [], 4: [], 5: []}
  2. 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}
  3. Find All Sources:

    • Sources are tasks with 0 in-degrees: sources = [0, 1]
  4. Process Each Source:

    • Process 0:
      • Remove 0 from sourcessources = [1]
      • Add 0 to sortedOrdersortedOrder = [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 sourcessources = []
      • Add 1 to sortedOrdersortedOrder = [0, 1]
      • For child 4 of 1, decrement inDegree[4]inDegree[4] = 0 → Add 4 to sourcessources = [4]
      • For child 3 of 1, decrement inDegree[3]inDegree[3] = 0 → Add 3 to sourcessources = [4, 3]
    • Process 4:
      • Remove 4 from sourcessources = [3]
      • Add 4 to sortedOrdersortedOrder = [0, 1, 4]
    • Process 3:
      • Remove 3 from sourcessources = []
      • Add 3 to sortedOrdersortedOrder = [0, 1, 4, 3]
      • For child 2 of 3, decrement inDegree[2]inDegree[2] = 0 → Add 2 to sourcessources = [2]
    • Process 2:
      • Remove 2 from sourcessources = []
      • Add 2 to sortedOrdersortedOrder = [0, 1, 4, 3, 2]
      • For child 5 of 2, decrement inDegree[5]inDegree[5] = 0 → Add 5 to sourcessources = [5]
    • Process 5:
      • Remove 5 from sourcessources = []
      • Add 5 to sortedOrdersortedOrder = [0, 1, 4, 3, 2, 5]
  5. Check for Cyclic Dependencies:

    • sortedOrder = [0, 1, 4, 3, 2, 5] contains all tasks.
  • Final order of tasks: [0, 1, 4, 3, 2, 5]

Code

Here is what our algorithm will look like:

Python3
Python3

. . . .

Time Complexity

In step ‘d’, each task can become a source only once and each edge (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.

Similar Problems

Course Schedule: There are ‘N’ courses, labeled from ‘0’ to ‘N-1’. Each course has some prerequisite courses which need to be completed before it can be taken. Given the number of courses and a list of prerequisite pairs, write a method to find the best ordering of the courses that a student can take in order to finish all courses.

Solution: This problem is exactly similar to our parent problem. In this problem, we have courses instead of tasks.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible