Jobs for the most profit
You are offered some jobs, given as three lists of the same length. Job i runs from time start[i] to time end[i] and pays profit[i]. You can work on one job at a time, so no two jobs you take may overlap. A job that ends at time t and a job that starts at time t do not overlap: you finish one and begin the other at the same moment.
Return the largest total profit from a set of jobs you can take. You do not have to take every job that fits.
start = [1, 3, 2, 5], end = [3, 5, 6, 7], profit = [20, 20, 50, 20]Output60Take the jobs from 1 to 3, 3 to 5 and 5 to 7: each one starts the moment the one before it ends. The 50 job, from 2 to 6, overlaps all three.
start = [1, 2, 4, 6], end = [10, 4, 6, 8], profit = [100, 30, 30, 30]Output100The long job pays more than the three short ones together, which make 90.
start = [1, 1, 1], end = [4, 3, 2], profit = [5, 8, 6]Output8All three jobs run between times 1 and 2, so only one can be taken.
1 ≤ len(start) = len(end) = len(profit) ≤ 5 × 104
1 ≤ start[i] < end[i] ≤ 109
1 ≤ profit[i] ≤ 104
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.