Loading...
Loading...
Loading...
Each job takes one hour, has a deadline hour and earns a profit if it finishes by its deadline. Hours are numbered from 1 and only one job runs per hour. Print the largest total profit.
Example 1
Input
5 2 100 1 19 2 27 1 25 3 15
Output
142
Example 2
Input
4 4 20 1 10 1 40 1 30
Output
60
Try the problem first. Open one hint at a time.
A job with a big deadline can fill an early hour only if nothing tighter needs it.
Sort by deadline and keep a min-heap of accepted profits; pop the smallest when the heap is longer than the deadline.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor