Deadline sequencing: hints, no solution
Medium · Greedy
A catering kitchen prepares one order at a time, and each order takes exactly one time unit. Order i must be finished by the end of time unit deadlines[i] (the first unit is number 1) and pays profits[i] if it is finished on time. An order that is late or skipped pays nothing. You choose which orders to make and in what sequence. Return the maximum total profit. Both arrays have the same length, and a deadline can be far larger than the number of orders.
Examples
- Input
- deadlines = [2, 2, 1, 3], profits = [40, 10, 30, 25]
- Output
- 95
- Note
- Make the 30 order in unit 1, the 40 order in unit 2 and the 25 order in unit 3. The 10 order has no free unit left before its deadline.
- Input
- deadlines = [1, 1, 1], profits = [5, 9, 7]
- Output
- 9
- Note
- Only one order can be finished by unit 1, so take the best.
- Input
- deadlines = [4, 4], profits = [3, 8]
- Output
- 11
Constraints
- 0 <= n <= 140000, where n is the number of orders
- 1 <= deadlines[i] <= 1000000000
- 1 <= profits[i] <= 100000
Hint 1: a nudge
Imagine every order is safe from lateness except for one shared clock. If two orders compete for the same time unit, which of them should you keep?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.