Maximum Order Volume
MediumDynamic Programming · Snowflake
A sales agent receives call requests. Each request is [start, duration, volume]: the call occupies the time interval from start to start + duration, and accepting it brings in volume units of orders.
The agent can take only one call at a time, so accepted calls must not overlap. A call that ends at time t does not overlap a call that starts at time t. Calls are given in no particular order.
Return the maximum total volume the agent can accept.
Example 1
- Input:
- calls = [[1, 4, 30], [2, 2, 25], [4, 3, 22], [6, 2, 15]]
- Output:
- 47
- Explanation
- The call
[2, 2, 25]ends at 4, exactly when[4, 3, 22]starts, so both can be taken for 47. Taking the 30-volume call (time 1 to 5) leaves room only for the last call, for 45.
Example 2
- Input:
- calls = [[0, 10, 50], [1, 3, 20], [5, 4, 25]]
- Output:
- 50
- Explanation
- The two short calls fit together for 45, but the single long call alone is worth 50.
Example 3
- Input:
- calls = [[5, 1, 4], [0, 2, 6], [2, 3, 8]]
- Output:
- 18
- Explanation
- Sorted by start time the calls run 0 to 2, 2 to 5 and 5 to 6. They chain without overlapping, so all three are accepted:
6 + 8 + 4 = 18.
Constraints
- 0 ≤
calls.length≤ 105 - 0 ≤
start≤ 109 - 1 ≤
duration≤ 109 - 1 ≤
volume≤ 106