Maximize profit of tasks startable before a deadline

Problem You are given duration[N] and profit[N] for N tasks and an integer T. Tasks run one at a time and, once started, run to completion. You may start a new task only before time T - 0.5. Executing tasks in any order you choose, maximize the total profit of tasks you manage to start.

Input / Output

• Input: arrays duration[], profit[], integer T.
• Output: maximum total profit obtainable.

Constraints

• 1 <= N <= 10^3
• 1 <= duration[i], T <= 10^4; profits are positive.

Example

• duration = [2, 3, 2], profit = [5, 6, 4], T = 5: ordering the two length-2 tasks first lets a third task still start before 4.5, so all three start in time → profit 15.