Maximize Profit of Tasks Startable Before a Deadline

You are given duration and profit for n tasks and an integer T. Tasks run one at a time, back to back from time 0, and once started, run to completion. You may start a new task only before time T - 0.5; a started task may finish after that. Executing tasks in any order you choose, return the maximum total profit of tasks you manage to start.

Example 1

Input:  duration = [2,3,2], profit = [5,6,4], T = 5
Output: 15

Ordering the two length-2 tasks first lets the third task still start at time 4, before 4.5, so all three start in time.

Example 2

Input:  duration = [1,5], profit = [1,10], T = 2
Output: 11

Run the short task first; the long one starts at time 1, before 1.5. It finishes at time 6, long after the deadline, and still counts. Running the long task first would block the short one.

Example 3

Input:  duration = [3,3,3], profit = [1,2,3], T = 4
Output: 5

Only two tasks can start (at times 0 and 3); the third would start at 6. Pick the two most profitable.

Constraints

• 1 <= duration.length == profit.length <= 10^3
• 1 <= duration[i], T <= 10^4
• 1 <= profit[i] <= 10^4