Schedule Jobs for the Most Profit

MediumGreedySortingArrays203 tests

You have n jobs. Job i has a deadline deadlines[i] and a profit profits[i].

Time is split into slots numbered 1, 2, 3, .... Every job takes exactly one slot, and only one job can run in each slot. Job i gives its profit only if it runs in a slot whose number is at most deadlines[i]. You do not have to run every job.

Choose which jobs to run, and when, so that the total profit is as large as possible.

Return an array [jobsDone, totalProfit]:

totalProfit is the largest total profit you can get.
jobsDone is the number of jobs in such a schedule. If several schedules give the largest total profit, use the largest number of jobs among them.

Hint: look at the jobs from the highest profit to the lowest. Put each job in the latest free slot that is not after its deadline. If there is no such slot, skip the job.

Examples

Example 1

Input:: [2,1,2,3,1], [40,25,30,15,60]
Output:: [3,115]

Four jobs have a deadline of 1 or 2. Only slots 1 and 2 can hold them, so at most two of those four jobs can run. The best two are profit 60 (slot 1) and profit 40 (slot 2). The job with profit 15 has deadline 3, so it runs in slot 3. Total: 60 + 40 + 15 = 115 with 3 jobs.

Example 2

Input:: [1,1,1], [7,9,4]
Output:: [1,9]

Every deadline is 1, so only slot 1 can be used. Run the job with profit 9.

Example 3

Input:: [3,3,3], [10,20,5]
Output:: [3,35]

Slots 1, 2 and 3 are all within the deadline of 3, so all three jobs can run: 10 + 20 + 5 = 35.

Constraints

1 <= n <= 12
deadlines.length == profits.length == n
1 <= deadlines[i] <= n
1 <= profits[i] <= 100

Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.