Maximum Profit in Job Scheduling

Problem You are given n jobs, each with a start time, an end time, and a profit. Select a subset of non-overlapping jobs (a job that ends at time t does not conflict with one that starts at t) that maximizes the total profit.

Input / Output

• Input: arrays start[], end[], profit[] of equal length n.
• Output: the maximum total profit achievable from a set of mutually non-overlapping jobs.

Constraints

• 1 <= n <= 5 x 10^4
• Times and profit fit in standard integer ranges; a greedy pick-by-profit does not work.

Example

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