Challenge
One execution engine can run at most one job at a time. Each opportunity [start, end, reward] occupies the half-open interval [start,end). Select any mutually nonoverlapping subset to maximise total reward and return that reward. Jobs may touch at an endpoint. You may reject every job; rewards may be negative. This is a deterministic scheduling model, not a forecast of real trading returns.
Input and output contract
0 ≤ n ≤ 30,000; 0 ≤ start < end ≤ 1,000,000; |reward| ≤ 1,000,000. Input order is arbitrary. Each row is a separate opportunity, including duplicate rows.
All tests follow this contract. You do not need to validate malformed input. Return the requested result from weighted_interval_scheduling; printed output is not your answer. Standard-library tools are allowed. Implement your solution in Python 3.12.
Target complexity: O(n log(n + 1)) time; O(n) 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
Arguments
[[[1, 3, 5], [2, 5, 6], [3, 6, 5], [6, 7, 4]]]
Expected return
14
Arguments
[[[0, 2, -5]]]
Expected return
0
Arguments
[[[0, 1, 4], [1, 2, 6]]]
Expected return
10
Hint
Sort by finishing time. For each job compare skipping it with taking its reward plus the optimum before its start.
The worked solution unlocks after completion, or with Premium access.