A school concert has n acts numbered 0 .. n-1; a lower number means the act's performers are younger and should go on stage sooner. rules holds pairs [a, b] meaning act a must perform before act b (to share props and costumes).
Among all running orders that obey every rule, pick the one that puts act 0 as early as possible; among those, the one that puts act 1 as early as possible; then act 2, and so on. (Equivalently: compare orders by the list [position of act 0, position of act 1, ...] and take the smallest.) Return that running order, or [] if no order obeys all the rules.
Examples
Input: n = 3, rules = [[2, 0]]
Output: [2, 0, 1]
Explanation: act 0 needs act 2 first, so position 1 is the earliest for act 0.
The order [1, 2, 0] starts with a smaller act but puts act 0 last.
Input: n = 5, rules = [[3, 0], [4, 1], [1, 0]]
Output: [4, 1, 3, 0, 2]
Explanation: act 0 needs 3, 1 and (through 1) 4 before it, so position 3 is its
earliest. Among such orders, act 1 can be second at best.
Input: n = 2, rules = [[0, 1], [1, 0]]
Output: []
Constraints
1 <= n <= 10**5,0 <= len(rules) <= 2 * 10**5,0 <= a, b < n,a != b; a rule may repeat- Target: O((n + R) log n) time. Scheduling each act's missing prerequisites one act at a time is too slow.
Goals
- See why taking the smallest ready item does not put small labels as early as possible
- Build the order backwards: run Kahn's algorithm on the reversed graph with a max-heap
- Detect a cycle and return the empty list