Courier slots
MediumOnline Assessment
Choose which parcels a courier delivers to earn the most in fees.
A courier makes at most one delivery per day, on days numbered 1, 2, 3, .... Each parcel in parcels is a pair [last_day, fee]: the parcel can be delivered on any one day from day 1 up to and including last_day, and delivering it earns fee. A parcel that is not delivered earns nothing. Each parcel can be delivered at most once, and the courier may skip days.
The courier does not work on closed_days (road closures, holidays): no delivery can happen on those days, but they still count as days in the calendar, so a parcel's last_day is a calendar day even when it falls on a closure.
Input: parcels, a list of [last_day, fee] pairs of positive integers, and closed_days, a list of distinct positive integers in increasing order.
Output: an integer, the largest total fee the courier can earn. If there are no parcels, or none can be delivered, return 0.
Deadlines can be as large as a billion and there can be hundreds of parcels, so trying every selection of parcels will be too slow.
Example 1
- Input:
- [[[2,10],[1,7],[2,5]],[]]
- Output:
- 17
- Explanation
- There are no closures. Day 1 can take the parcel due on day 1 (fee 7) and day 2 the parcel worth 10, for 17. The parcel worth 5 would need a third day within its deadline, which does not exist.
Example 2
- Input:
- [[[3,4],[3,9],[2,6],[3,5]],[2]]
- Output:
- 15
- Explanation
- Day 2 is closed. Open days up to day 3 are days 1 and 3, and only day 1 is open by day 2. The parcel
[2, 6]must go on day 1 and the parcel[3, 9]on day 3, for 15. The other two parcels have no open day left.
Example 3
- Input:
- [[[1000000000,5],[1000000000,8],[1,3]],[1]]
- Output:
- 13
- Explanation
- Day 1 is closed, so the parcel
[1, 3]can never be delivered. The two parcels with huge deadlines go on days 2 and 3, for 5 + 8 = 13.
Constraints
0 <= parcels.length <= 1,0001 <= last_day <= 1,000,000,000and1 <= fee <= 1,000,000for every parcel0 <= closed_days.length <= 500, strictly increasing, each between1and1,000,000,000