Frontend School

Project Task Prioritization

DSA
hard

Project Task Prioritization

Hard
Graph
Topological Sort
Priority Queue
Kahn's Algorithm

Overview

Twitter's engineering teams manage complex projects with many interdependent tasks. To ensure critical features ship on time, some tasks are marked as high priority. We need a system to generate a valid task execution order that respects all dependencies while prioritizing high-priority tasks to appear as early as possible in the schedule. This ensures that work on crucial components starts without unnecessary delays, optimizing project timelines and resource allocation.

What you need to do / Task

Implement a function prioritizeTasks that takes the total number of tasks, a list of their dependencies, and a set of high-priority task IDs. The function should return a valid topological sort of the tasks. If multiple valid topological sorts exist, the one that places high-priority tasks earliest in the sequence is preferred. Dependencies must always be respected.

Input & output

  • numTasks: number The total number of tasks, labeled from 0 to numTasks - 1.
  • dependencies: number[][] A list of dependency pairs, where [u, v] means task u must be completed before task v can start. Each inner array [u, v] represents a directed edge from u to v.
  • highPriorityTasks: number[] A list of task IDs that are considered high priority.

Return: number[] A list of task IDs representing a valid topological sort. If a cycle is detected in the dependencies, return an empty array [].

Clarifications

  • Empty highPriorityTasks: If the highPriorityTasks list is empty, all tasks should be treated as normal priority. In this scenario, any valid topological sort is acceptable, but for consistency, ties between normal priority tasks should be broken by their numerical ID (smaller ID first).
  • Dependency precedence: Dependencies are absolute. A high-priority task cannot be scheduled before its prerequisites are met.
  • Task ID uniqueness: Task IDs range from 0 to numTasks - 1 and are unique.

Examples

1

Example 1

Input:

numTasks = 4, dependencies = [[0, 1], [0, 2], [1, 3], [2, 3]], highPriorityTasks = [2]

Output:

[0, 2, 1, 3]

Note:

Tasks 0, 1, 2, 3. Task 2 is high priority. Initially, only task 0 is ready. After 0, tasks 1 and 2 are ready. Since 2 is high priority, it's picked before 1. Then 1, then 3.

2

Example 2

Input:

numTasks = 5, dependencies = [[0, 3], [1, 3], [2, 4]], highPriorityTasks = [1, 2]

Output:

[1, 2, 0, 3, 4]

Note:

Tasks 0, 1, 2, 3, 4. Tasks 1 and 2 are high priority. Initially, 0, 1, 2 are ready. High priority tasks 1 and 2 are picked first (tie-broken by ID), then 0. This affects when tasks 3 and 4 become ready.

3

Example 3

Input:

numTasks = 3, dependencies = [[0, 1], [1, 2], [2, 0]], highPriorityTasks = [0]

Output:

[]

Note:

The dependencies form a cycle (0 -> 1 -> 2 -> 0). No valid topological sort exists, so an empty array is returned.

Constraints

Constraints & assumptions

  • 1 <= numTasks <= 10^5
  • 0 <= dependencies.length <= min(numTasks * (numTasks - 1) / 2, 10^5)
  • 0 <= u, v < numTasks for any [u, v] in dependencies
  • u != v for any dependency [u, v]
  • 0 <= highPriorityTasks.length <= numTasks
  • All task IDs in highPriorityTasks are unique and within the range [0, numTasks - 1].

Out of scope

  • Optimizing for minimum total schedule time (e.g., considering task durations).
  • Handling resource conflicts beyond simple task dependencies.
  • Complex priority schemes (e.g., multiple priority levels, dynamic priorities).

What interviewers evaluate

  • Correctly models task dependencies as a directed graph (adjacency list and in-degrees).
  • Applies Kahn's algorithm (or a DFS-based topological sort) effectively.
  • Successfully integrates priority logic using a priority queue or similar mechanism to prioritize high-priority tasks among ready tasks.
  • Gracefully handles cyclic dependencies by detecting them and returning an empty array.
  • Achieves optimal time and space complexity for the given constraints.

Loading editor...