FunctionRacerProblemsRace

Best Job Lineup

MediumGreedyPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Greedy problems