Best Job Lineup
You can do at most one job per day and each job takes exactly one day. Job i pays profits[i], but only if it is done on day deadlines[i] or earlier; days are numbered from 1. Jobs you never do pay nothing. Return the largest total profit you can earn. Return 0 if there are no jobs.
Example 1
profits [100,19,27,25,15]
deadlines [2,1,2,1,3]
returns 142
Do the 27 job on day 1, the 100 job on day 2 and the 15 job on day 3: 142. The 25 and 19 jobs both need day 1, which is better spent on 27.
Example 2
profits [20,15,10,5,1]
deadlines [2,2,1,3,3]
returns 40
Day 1 takes the 15 job, day 2 the 20 job, day 3 the 5 job; the 10 job needed day 1 and the 1 job needed a day at or before 3, all taken.
Constraints
0 <= len(profits) == len(deadlines) <= 1001 <= profits[i] <= 10001 <= deadlines[i] <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.