Maximum Profit in Job Scheduling

Problem You are given n jobs, each with a start time, end time, and profit. Choose a subset of non-overlapping jobs that maximizes total profit. A job ending at time t does not conflict with a job starting at time t.

Input / Output

• Input: three arrays startTime, endTime, profit of equal length n.
• Output: the maximum total profit from a set of non-overlapping jobs.

Constraints

• Up to 5·10^4 jobs; times up to 10^9 (so a DP cannot index by time directly).
• Because profits vary, the greedy "pick the job that ends earliest" rule used for unweighted interval scheduling does not maximize profit.

Example

• start=[1,2,3,3], end=[3,4,5,6], profit=[50,10,40,70] → 120 (jobs 1 and 4).