A pottery kiln runs one firing job per unit-length time slot (slots numbered 1, 2, 3, ...). There are n jobs. Job i takes exactly one slot, must be placed in a slot no later than its deadline d[i] ≥ 1, and pays a bounty p[i] > 0 if it is run. You may run any subset of jobs, at most one per slot, and each chosen job must occupy some slot t ≤ d[i].
Maximize the total bounty of the jobs you run.
Line 1: an integer n.
Next n lines: two integers d and p — the deadline and the bounty of one job.
A single integer: the maximum total bounty attainable.
Example 1
Input
3 1 20 2 15 2 10
Expected
35
Explanation
Take bounty 20 in slot 1 and bounty 15 in slot 2. The bounty-10 job also needs a slot ≤ 2, but both are taken, so it is dropped. Total 35.
Example 2
Input
2 1 10 1 5
Expected
10
Explanation
Both jobs need slot 1, so only one can run; keep the larger bounty 10.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →