Dependency-Aware Task Scheduler
Rippling● MediumFULLTIMEPHONE SCREENProblem statement
You are given unique task identifiers, dependency edges, integer priorities, and a filter decision for every task. A dependency [before, after] means before must appear before after.
Only tasks whose included value is true participate. Ignore a dependency edge when either endpoint is filtered out. Repeatedly choose a currently ready task with the greatest priority; break ties by the lexicographically smaller task identifier.
Return the deterministic schedule. If the retained dependency graph contains a cycle, return an empty array.
Function
scheduleTasks(taskIds: String[], dependencies: String[][], priorities: int[], included: boolean[]) → String[]Examples
Example 1
taskIds = ["extract","clean","load","audit"]dependencies = [["extract","clean"],["clean","load"]]priorities = [2,5,4,9]included = [true,true,true,true]return = ["audit","extract","clean","load"]Audit is initially ready with the greatest priority. The remaining dependency chain must then run in order.
Example 2
taskIds = ["a","b","c"]dependencies = [["a","b"],["b","c"]]priorities = [1,10,5]included = [false,true,true]return = ["b","c"]Filtering removes task a and its incident edge. Task b is then ready before c.
Example 3
taskIds = ["a","b"]dependencies = [["a","b"],["b","a"]]priorities = [1,2]included = [true,true]return = []No retained task has zero indegree, so the retained graph is cyclic.
Constraints
1 <= taskIds.length == priorities.length == included.length <= 20000.- Task identifiers are unique nonempty ASCII strings.
-10^9 <= priorities[i] <= 10^9.0 <= dependencies.length <= 50000; every edge contains two known, different identifiers and edges are distinct.