Curated Production Pipeline
Spotify's content pipeline involves numerous steps from initial recording to final release. To ensure a smooth and efficient workflow, and to meet crucial deadlines for high-priority tracks, it's essential to properly sequence these production tasks. This problem simulates a simplified version of such a pipeline, where tasks have dependencies and some are critical with specific completion deadlines.
You are given a set of production tasks, their dependencies, and a list of critical tasks with associated deadlines. Your goal is to determine a valid ordering of tasks such that all dependencies are met, and all critical tasks are completed by their respective deadlines.
numTasks: An integer representing the total number of unique production tasks, labeled from 0 to numTasks - 1.dependencies: An array of pairs [fromTask, toTask], where fromTask must be completed before toTask can begin.criticalTasks: An array of pairs [taskId, maxPosition], where taskId is a critical task that must appear at an index <= maxPosition in the final ordered sequence (0-indexed).Return: An array of numbers representing any valid topological order of tasks that satisfies all dependencies and critical task deadlines. If no such order exists (due to a cycle or an unmet critical deadline), return an empty array [].
0 to numTasks - 1.dependencies is empty, tasks can be ordered arbitrarily, subject to criticalTasks constraints.criticalTasks is empty, only dependency constraints need to be satisfied.maxPosition for critical tasks is 0-indexed. So, a maxPosition of 0 means the task must be the very first task in the sequence.Examples
Example 1
Input:
numTasks = 4, dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]], criticalTasks = [[0, 3]]
Output:
[3,1,2,0]
Note:
A valid order is [3, 1, 2, 0]. Task 0 is critical and must be at position <= 3. It's at position 3, which satisfies the condition. Another valid output could be [3,2,1,0].
Example 2
Input:
numTasks = 3, dependencies = [[0, 1], [1, 2], [2, 0]], criticalTasks = []
Output:
[]
Note:
The dependencies form a cycle (0 -> 1 -> 2 -> 0), so no valid topological order can exist. An empty array is returned.
Example 3
Input:
numTasks = 4, dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]], criticalTasks = [[0, 1]]
Output:
[]
Note:
In any valid topological order, tasks 1 and 2 must come before task 0, and task 3 must come before tasks 1 and 2. This means task 0 will always be at position 2 or 3 (e.g., [3,1,2,0] or [3,2,1,0]). Since task 0 is critical and must be at position <= 1, its deadline cannot be met. An empty array is returned.
Example 4
Input:
numTasks = 2, dependencies = [], criticalTasks = [[0, 0], [1, 1]]
Output:
[0,1]
Note:
No dependencies, so tasks can be ordered freely. Task 0 must be at position 0, Task 1 must be at position <= 1. The order [0, 1] satisfies both. The order [1, 0] would violate Task 0's critical deadline (1 <= 0 is false), so [0, 1] is the only valid sequence.
Constraints
1 <= numTasks <= 10^50 <= dependencies.length <= 2 * 10^50 <= criticalTasks.length <= numTaskstaskIds in dependencies and criticalTasks are valid: 0 <= taskId < numTasks.0 <= maxPosition < numTasks for all critical tasks.[A, A]).O(V+E) complexity).Loading editor...