Maximum Profit in Job Scheduling

Problem Jobs have (startTime, endTime, profit). Choose non-overlapping jobs (a job ending at t allows another starting at t) maximizing total profit.

Input / Output

• Input: arrays startTime, endTime, profit. Output: max profit.

Constraints

• Up to 5*10^4 jobs; times to 10^9 → O(n log n) DP + binary search; the unweighted trick (greedy by end) does NOT work with profits — say why.

Example

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

Expected approach

• Weighted interval scheduling: sort by end time; dp[i] = max(dp[i−1] [skip], profit[i] + dp[p(i)] [take]) where p(i) = last job ending <= start[i], found by binary search over sorted ends. O(n log n)/O(n). The heap alternative (sort by start, pop settled intervals maintaining best-so-far) is equivalent — know one cold. Follow-ons: reconstruct the chosen set, at-most-k jobs (extra DP dimension).