Frontend School

Project Task Scheduling

DSA
medium

Project Task Scheduling

Medium
Graph
Topological Sort
Directed Acyclic Graph

Overview

In complex software development or project management, tasks often have intricate dependencies. For instance, 'implement feature X' might require 'design database schema Y' to be completed first. Efficiently scheduling these tasks is crucial for project success. This problem challenges you to determine a valid execution sequence for a set of project tasks, ensuring all prerequisites are met, or identify if such a sequence is impossible due to circular dependencies.

What you need to do / Task

Implement the findTaskOrder function that takes the total number of tasks and their prerequisites as input. Your goal is to:

  1. Construct a dependency graph from the given tasks and prerequisites.
  2. Find any valid topological ordering of the tasks such that for every prerequisite [task, prerequisite], prerequisite comes before task in the returned order.
  3. If a valid ordering is impossible to achieve due to circular dependencies, return an empty array [].

Input & output

Function Signature

function findTaskOrder(n: number, prerequisites: number[][]): number[]

Parameters

  • n: An integer representing the total number of tasks. Tasks are labeled from 0 to n-1.
  • prerequisites: An array of pairs [task, prerequisite]. Each pair indicates that task cannot be started until prerequisite is completed. In graph terms, there's a directed edge from prerequisite to task.

Return Value

  • An array of integers representing a valid topological ordering of tasks. If multiple valid orders exist, any one is acceptable.
  • If no such order exists (i.e., there is a circular dependency), return an empty array [].

Clarifications

  • Empty input: If prerequisites is empty, any order of tasks 0 to n-1 is valid. For example, [0, 1, ..., n-1]. If n=0, an empty array [] should be returned.
  • Multiple valid orders: If there are multiple valid topological sorts, your function can return any one of them.

Examples

1

Example 1

Input:

n = 2, prerequisites = [[1,0]]

Output:

[0,1]

Note:

Task 0 has no prerequisites. Task 1 depends on Task 0. A valid order is [0, 1].

2

Example 2

Input:

n = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output:

[0,1,2,3]

Note:

Task 0 has no prerequisites. Task 1 depends on 0. Task 2 depends on 0. Task 3 depends on 1 and 2. A valid order is [0, 1, 2, 3]. Another valid order would be [0, 2, 1, 3].

3

Example 3

Input:

n = 3, prerequisites = [[1,0],[0,1]]

Output:

[]

Note:

Task 1 depends on Task 0, and Task 0 depends on Task 1, forming a circular dependency. It's impossible to complete both tasks, so no valid order exists.

Constraints

Constraints & assumptions

  • 1 <= n <= 10^5
  • 0 <= prerequisites.length <= min(n * (n - 1) / 2, 10^5)
  • Each prerequisite[i] is a pair [task_i, pre_i].
  • 0 <= task_i, pre_i < n
  • task_i != pre_i (A task cannot be its own prerequisite).
  • All pairs [task, prerequisite] in prerequisites are unique.

What interviewers evaluate

  • Algorithm Correctness: Correctly identifies and handles circular dependencies, returning an empty array when a cycle is present.
  • Graph Representation: Constructs an appropriate graph data structure to represent task dependencies.
  • Topological Sort Implementation: Applies an efficient and correct topological sort algorithm (e.g., Kahn's algorithm using in-degrees, or DFS-based approach).
  • Time and Space Complexity: Achieves optimal or near-optimal time and space complexity for the given constraints (ideally O(N + M) time and O(N + M) space, where N is the number of tasks and M is the number of prerequisites).

Loading editor...