All problems

Urgent Test Order

Medium · topological sort

A clinic has n lab tests, numbered 0 to n - 1. Test i has an urgency of urgency[i]: the bigger the number, the more urgent the test. The lab can run only one test at a time.

Some tests need another test done first. Each pair [a, b] in needs means test a must be run before test b. A test is ready when every test it needs has already been run.

The lab always runs the ready test with the highest urgency. If several ready tests share that urgency, it runs the one with the smaller number. Return the numbers of the tests in the order they are run.

If the lab gets stuck before running every test (some tests wait on each other in a loop), return an empty list. The same pair may appear more than once, and a pair may name a test as needing itself.

Examples

Example 1

Input: urgency = [4, 9, 4], needs = []

Output: [1, 0, 2]

Test 1 is the most urgent. Tests 0 and 2 tie, so the smaller number goes first.

Example 2

Input: urgency = [2, 9, 4], needs = [[2, 1]]

Output: [2, 1, 0]

Test 1 is the most urgent but needs test 2, so test 2 runs first (it beats test 0). Then test 1 is ready and goes before test 0.

Example 3

Input: urgency = [1, 1], needs = [[0, 1], [1, 0]]

Output: []

Each test needs the other, so neither is ever ready.

Constraints