0% completed

All Tasks Scheduling Orders (hard)

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 print all possible ordering of tasks meeting all prerequisites.

Examples

Example 1:

Input: Tasks=4, Prerequisites=[3, 2], [3, 0], [2, 0], [2, 1]
Output: 
1) [3, 2, 0, 1]
2) [3, 2, 1, 0]
Explanation: There are two possible orderings of the tasks meeting all prerequisites.

Example 2:

.....

Like the course? Get enrolled and start learning!

M

Micky M

· 4 years ago

Mohammed Dh Abbas

· 2 years ago

The official solution is bad and disagree with how it was done. how uses queue.remove() ???. that's O(operation)

This is a the proper solution to the question

from collections import deque

class Solution:
  def __init__(self):
    self.orders = []

  # this is a backtracking / permutatinal + topological solution
  def topo(self, path, seen):
    
    # base case
    if len(path) == len(self.graph):
      self.orders.append(path[:])
      return

    # instead of using queue to procee the next 0 node we recurse and loop to find the 0 node
    for node in self.graph:
      if self.indegree[node] == 0 and not seen.get(node):

        seen[node] = True
        path.append(node)

        for nex_node in self.graph[node]:
          self.indegree[nex_node] -= 1

        self.to

L

lejafilip

· 2 years ago

Ankit Joshi

· a year ago