0% completed

Tasks Scheduling (medium)

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

.....

Like the course? Get enrolled and start learning!

R

Ray

· 4 years ago

Hey the JS solution has this:

console.log(`Is scheduling possible: ${
is_scheduling_possible(6, [
[0, 4],
[1, 4],
[3, 2],
[1, 3],
])}`);

It's missing the first 2 tuples in 2nd arg: [2, 5], [0, 5],

Show 1 reply

S

Saiful I

· 2 years ago

Trang Luong

· a year ago

from collections import deque, defaultdict

class Solution:
  # def isSchedulingPossible(self, tasks, prerequisites):
  #   # basically find out if there's a cycle in this graph
  #   # [2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3] 6
  #   in_degree = [0] * tasks # [0, 0, 1, 0, 0, 1]
  #   adj_list = defaultdict(list) # {2: [5], 0: [5, 4], 1: [4, 3], 3: [2]}
  #   for prev_task, task in prerequisites:
  #     adj_list[prev_task].append(task)
  #     in_degree[task] += 1
  #   top_sort_result = [] # 0 1 
  #   queue = deque()
  #   for task in range(len(in_degree)):
  #     if in_degree[task] == 0:
  #       queue.append(task)
  #   while queue: # [4, 3]
  #     task = queue.popleft() # 0 1
  #     top_sort_result.append(task) 
  #     for neighbor in adj_list[task]: # 4 3

M

mailman14736

· 22 days ago