Pickup Slot Capacity
MediumScheduling · Walmart
A store offers curbside pickup slots. slots is a list of [slot_time, capacity] sorted by slot_time ascending, with distinct times; each slot can serve at most capacity orders. orders is a list of [order_id, ready_time, expire_time]: the order can be picked up at any slot whose time is in the inclusive range [ready_time, expire_time].
Process orders one at a time in list order. Assign each order to the earliest slot in its range that still has capacity left, and use up one unit of that slot's capacity. If no such slot exists, the order is assigned "NONE". Assignments are final: a later order never moves an earlier one.
Return a list of [order_id, assigned_slot_time] rows in the same order as orders, where assigned_slot_time is the slot's time or the string "NONE".
With up to 10^5 orders and slots, scanning every slot for every order is too slow.
Example 1
- Input:
- orders = [[1, 10, 30], [2, 10, 20], [3, 15, 40], [4, 5, 8]], slots = [[10, 1], [20, 1], [30, 2]]
- Output:
- [[1, 10], [2, 20], [3, 30], [4, "NONE"]]
- Explanation
- Order 1 takes slot 10, its only seat. Order 2 finds 10 full and takes 20. Order 3 can use 20 or later, but 20 is now full, so it gets 30. No slot lies in order 4's range
[5, 8].
Example 2
- Input:
- orders = [[7, 0, 50], [8, 0, 50]], slots = [[5, 0], [25, 1]]
- Output:
- [[7, 25], [8, "NONE"]]
- Explanation
- Slot 5 has capacity 0 and is never usable, so order 7 takes slot 25 and order 8 finds nothing left.
Example 3
- Input:
- orders = [[1, 20, 20], [2, 21, 29]], slots = [[20, 1], [30, 1]]
- Output:
- [[1, 20], [2, "NONE"]]
- Explanation
- Order 1's range is exactly
[20, 20], which includes slot 20. Order 2 needs a slot between 21 and 29, and there is none.
Constraints
0 <= orders.length, slots.length <= 10^5slotsis sorted byslot_timeascending and the times are distinct0 <= capacity <= 10^50 <= ready_time <= expire_time <= 10^9,0 <= slot_time <= 10^9, and order ids are distinct integers