Project Task Prioritization
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.
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.
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 [].
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).0 to numTasks - 1 and are unique.Examples
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.
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.
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
1 <= numTasks <= 10^50 <= dependencies.length <= min(numTasks * (numTasks - 1) / 2, 10^5)0 <= u, v < numTasks for any [u, v] in dependenciesu != v for any dependency [u, v]0 <= highPriorityTasks.length <= numTaskshighPriorityTasks are unique and within the range [0, numTasks - 1].Loading editor...