All problems

Delivery Deadlines

Medium · greedy

A courier has a list of parcels. Each parcel is a pair [deadline, tip]: if it is delivered on day d with d <= deadline, the courier earns tip. A parcel delivered after its deadline earns nothing, so it is simply skipped.

Days are numbered 1, 2, 3, ... and the courier delivers at most one parcel per day. A parcel takes exactly one day, and any parcel can be delivered on any day up to its deadline.

Return the largest total tip the courier can earn.

Examples

Example 1

Input: parcels = [[2, 50], [1, 20], [2, 30], [1, 10]]

Output: 80

No parcel can wait past day 2, so only two parcels can go. The two 2-deadline parcels, 50 and 30, take days 2 and 1 for a total of 80.

Example 2

Input: parcels = [[1, 7], [1, 9], [1, 4]]

Output: 9

All three must go on day 1, so only the best one counts.

Example 3

Input: parcels = [[5, 3], [5, 8]]

Output: 11

Constraints