Maximize profit of tasks startable before a deadline

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.

Expected approach

• Only the start time matters: the k-th started task begins at the prefix sum of earlier durations, so a chosen set is feasible iff its tasks can be ordered with every start time < T - 0.5.
• Run a 0/1 knapsack over a time budget: dp[t] = max profit using start-time budget t (t up to T - 1). For each task, dp[t] = max(dp[t], dp[t - duration] + profit).
• Equivalent to weighted job selection under a time budget; O(N · T).