Storage Bin Assignment
MediumSimulation · Amazon
A warehouse has a row of storage bins. capacities[j] is the remaining capacity of bin j. Items arrive one at a time in the order given by items, where items[i] is the weight of item i.
Each item goes into the lowest-index bin whose remaining capacity is at least the item's weight, and that bin's remaining capacity drops by the item's weight. If no bin can hold the item, the item is turned away and nothing changes.
Return a list the same length as items whose i-th entry is the index of the bin item i was placed in, or -1 if it was turned away. You may modify capacities.
Example 1
- Input:
- items = [4, 3, 6, 2], capacities = [7, 5, 6]
- Output:
- [0, 0, 2, 1]
- Explanation
- The 4 goes in bin 0 (7 left 3). The 3 still fits bin 0 exactly, so it goes there rather than in a roomier later bin. The 6 does not fit bin 0 (0 left) or bin 1 (5), so it goes in bin 2. The 2 then skips the empty bin 0 and lands in bin 1.
Example 2
- Input:
- items = [5, 9, 1], capacities = [4, 8]
- Output:
- [1, -1, 0]
- Explanation
- The 5 is too big for bin 0 (4) and goes in bin 1, leaving 3. The 9 fits nowhere and gets
-1. The 1 fits bin 0, the lowest index with room.
Example 3
- Input:
- items = [2, 2, 2], capacities = [3, 3]
- Output:
- [0, 1, -1]
- Explanation
- Each of the first two items takes a bin and leaves it with 1 unit. The third item weighs 2, so it fits neither bin.
Constraints
0 <= items.length <= 10^50 <= capacities.length <= 10^51 <= items[i] <= 10^90 <= capacities[j] <= 10^9