Schedule Unit Jobs Before Their Deadlines for Maximum Profit
Implement maxJobProfit
You have several jobs, each taking exactly one unit of time and each with a deadline and a profit. Only one job can run in any time unit (units are numbered 1, 2, 3, …), and a job earns its profit only if it runs in some unit up to its deadline. Jobs may be skipped. Find the maximum total profit.
Checking every subset of jobs for feasibility works but grows exponentially. The greedy approach considers jobs from most to least profitable and drops each one into the latest still-free time unit at or before its deadline, skipping it if none is free.
Example 1:
Input: deadlines = [2,3,1,3,2], profits = [35,20,50,25,40]
Output: 115
Example 2:
Input: deadlines = [1,1,1,1], profits = [5,12,8,3]
Output: 12
Example 3:
Input: deadlines = [1], profits = [9]
Output: 9
+ 9 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ deadlines.length ≤ 12, and profits.length equals deadlines.length - ●
1 ≤ deadlines[i] ≤ 15 and 1 ≤ profits[i] ≤ 100 - ●
Every job takes exactly one time unit, and only one job can run in each time unit (units are numbered 1, 2, 3, …) - ●
Job i earns profits[i] only if it runs in a time unit from 1 up to deadlines[i]; a job may also be skipped. Return the maximum total profit
deadlines =
profits =