Job Sequencing with Deadlines
MediumP3Coding
There are n jobs. Job i takes one unit of time, has a deadline deadlines[i] (it must finish by the end of time unit deadlines[i], with time units numbered from 1), and earns profits[i] if it is completed by then. Only one job can run in each time unit.
Return [count, totalProfit]: the number of jobs done and the total profit, for a schedule that maximises the total profit. All profits are positive.
Example 1
- Input
- deadlines = [4,1,1,1], profits = [20,10,40,30]
- Output
- [2,60]
- Why
- Do the profit-40 job in slot 1 and the profit-20 job in a later slot.
Example 2
- Input
- deadlines = [2,1,2,1,1], profits = [100,19,27,25,15]
- Output
- [2,127]
Constraints
- 1 <= n <= 10^5
- 1 <= deadlines[i] <= n
- 1 <= profits[i] <= 500
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 10. ⌘Enter runs, ⌘⇧Enter submits.