Course Dependencies and Earliest Completion

Challenge

Courses are numbered 0..n-1 with positive integer durations. Each prerequisite [before, after] means before must finish before after can start. Unlimited courses can run in parallel; they may start at time zero if ready. Return {"order": [...], "completion_times": [...], "total_time": T}. Order is the lexicographically smallest valid topological order. Completion_times[i] is course i’s earliest finish, and T is the earliest finish of every course. If any dependency cycle exists, return null (None). Duplicate prerequisite pairs count only once.

Input and output contract

0 ≤ n ≤ 1,500; duration 1..1,000; ≤6,000 prerequisite pairs with valid endpoints. Self-dependencies are cycles. Empty input returns {"order": [], "completion_times": [], "total_time": 0}. The ordering output does not imply courses run sequentially.

All tests follow this contract. You do not need to validate malformed input. Return the requested result from course_dependencies; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.

Target complexity: O(e + n log(n + 1)) expected time; O(n + e) auxiliary space

Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.

Public examples

[[3, 2, 4, 1], [[0, 2], [1, 2], [2, 3]]]

{'order': [0, 1, 2, 3], 'total_time': 8, 'completion_times': [3, 2, 7, 8]}

[[1, 1], [[0, 1], [1, 0]]]

None

[[], []]

{'order': [], 'total_time': 0, 'completion_times': []}

The worked solution unlocks after completion, or with Premium access.