Smallest Task Order
There are len(needs) tasks numbered from 0. needs[i] lists the tasks that must be finished before task i can start; a list may repeat a task, and a task never needs itself.
Return a list of all the tasks in an order that respects every requirement. When more than one order is valid, return the lexicographically smallest one: at the first position where two valid orders differ, pick the one with the smaller task number. Return the empty list [] if no valid order exists.
Example 1
Task 0 needs nothing; tasks 1 and 2 both wait for it. Of the valid orders, [0, 1, 2] is smallest.
Example 2
Tasks 0 and 2 both need task 1, so 1 goes first, then 0 before 2.
Constraints
1 <= len(needs) <= 500 <= needs[i][j] < len(needs)andneeds[i][j] != i- At most 100 entries in total
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Smallest Team SplitMedium
- Steps to the ExitMedium
- Through the CheckpointMedium
- Towns Within BudgetMedium
- Break Through WallsHard
- Collect Every KeyHard
- Count the BridgesHard
- Critical JunctionsHard