681. Course Order
A training academy runs n workshops numbered 0 to n - 1. Some workshops can only be attended after others: each entry [x, y] in prerequisites means workshop x must be finished before workshop y begins. Entries may repeat.
Return a schedule that attends every workshop exactly once while respecting all of these rules. If several schedules work, any valid one is accepted. If the rules contradict each other (for example they form a loop, including a workshop that must precede itself), return an empty array.
Aim for O(n + m) time, where m is the number of entries in prerequisites.
Example 1
- Input:
- n = 5, prerequisites = [[3,1],[1,4],[3,0],[0,2]]
- Output:
- [3,1,0,4,2]
- Explanation:
Workshop 3 has no rules, then 1 and 0 unlock, then 4 and 2; the schedule 3, 1, 0, 4, 2 respects every rule (other valid schedules are also accepted).
Example 2
- Input:
- n = 3, prerequisites = [[0,1],[1,2],[2,0]]
- Output:
- []
- Explanation:
Each workshop waits for another in a loop, so no schedule exists and the answer is empty.
Example 3
- Input:
- n = 1, prerequisites = []
- Output:
- [0]
- Explanation:
A single workshop with no rules is scheduled alone.
Constraints
1 ≤ n ≤ 100000
0 ≤ prerequisites.length ≤ 200000
prerequisites[i] = [x, y] with 0 ≤ x, y < n; pairs may repeat and x may equal y
How this problem is judged
- Answers
- Any valid answer is accepted. A checker tests yours against the problem's rules.
- Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)