Problem · Graph
Resolve Task Dependencies
Learn this problem● Hard
AmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insightsAmazonFULLTIMEONSITE INTERVIEWProblem statement
There are n tasks numbered from 0 through n - 1. A dependency [u, v] means task u must be completed before task v.
The array mandatory contains dependencies that cannot be removed. Each row [u, v, cost] in optional contains a removable dependency u -> v and its cost.
- If the graph containing every dependency is acyclic, return its lexicographically smallest topological order without removing anything.
- If it is cyclic, consider removing exactly one optional dependency. Among the optional dependencies whose removal makes the entire graph acyclic, remove the one with the smallest cost. If costs tie, remove the one appearing earlier in
optional. Return the lexicographically smallest topological order of the resulting graph. - If no single optional dependency can make the graph acyclic, return an empty array.
Function
resolveTaskOrder(n: int, mandatory: int[][], optional: int[][]) → int[]Examples
Example 1
n = 4mandatory = [[0,1],[2,3]]optional = [[1,2,7]]return = [0,1,2,3]All dependencies are already acyclic, so none is removed. The only valid order is [0,1,2,3].
Example 2
n = 3mandatory = [[0,1]]optional = [[1,2,5],[2,0,2]]return = [0,1,2]The dependencies form the cycle 0 -> 1 -> 2 -> 0. Removing 2 -> 0 costs 2, which is cheaper than removing 1 -> 2.
Example 3
n = 2mandatory = [[0,1],[1,0]]optional = []return = []The mandatory dependencies form a cycle, and there is no optional dependency that can be removed.
Constraints
1 <= n <= 5000 <= mandatory.length, optional.lengthmandatory.length + optional.length <= 2000- Every dependency endpoint is in
[0, n - 1], and no dependency is repeated. 0 <= cost <= 1000000000