hardDynamic Programming 1DPure DSA~45 min
Weighted Task Scheduling Max Profit
A single worker can run one job at a time. Each job has a start time, an end time, and a payout. Overlapping jobs can't both run. Choose a non-overlapping subset that maximizes total payout.
Problem
Given arrays startTime, endTime, and profit of equal length, where job i runs on [startTime[i], endTime[i]) for profit[i], return the maximum profit from a subset of non-overlapping jobs. A job may start exactly when another ends.
Input
Three arrays of length n (1 ≤ n ≤ 5·10^4); times up to 10^9, profit up to 10^4.
Output
An integer: the maximum achievable profit.
Constraints
- Jobs may overlap arbitrarily
- A job starting at time t does not conflict with one ending at t
- Profits are positive
Examples
Example 1
Input
start = [1,2,3,3], end = [3,4,5,6], profit = [50,10,40,70]
Output
120
Run job 0 (1–3, 50) and job 3 (3–6, 70) for 120.
Example 2
Input
start = [1,2,3,4,6], end = [3,5,10,6,9], profit = [20,20,100,70,60]
Output
150
Jobs ending early then 3–10 (100) plus 4–6 (70) is suboptimal; the best total is 150.