Bakery Pickup Tray Alignment
Lexicographically smallest minimum-cost ordered matching of two arrays
A bakery has pickup orders arranged in customer arrival order and prepared pastry trays arranged along a conveyor.
requested[i] is the desired pastry weight for order i. Tray j has weight weights[j] and an adjustment charge charges[j]. A charge may be negative, representing a promotional credit.
Assign exactly one tray to every order. Each tray can be used at most once, and assignments must preserve conveyor order: if order i receives tray j, every later order must receive a tray with a larger index. Unused trays may be left on the conveyor.
Assigning tray j to order i costs:
abs(requested[i] - weights[j]) + charges[j]
Return the zero-based tray indices, in order of their assigned orders, that minimize the total cost. If several assignments have the same minimum cost, return the lexicographically smallest index list: at the first differing position, the list with the smaller index wins.
If there are no orders, return an empty list.
Examples
Example 1
Input: requested = [4,8], weights = [3,5,8], charges = [0,0,0] Output: [0,2]
The first order can use the tray weighing 3, while the second can use the tray weighing 8. Leaving the middle tray unused avoids a larger weight mismatch.
Example 2
Input: requested = [5,5], weights = [5,5,5,5], charges = [2,2,2,2] Output: [0,1]
All trays have the requested weight and identical charges, so every increasing selection of two trays has the same cost. The tie is resolved by choosing the earliest possible indices.
Example 3
Input: requested = [10], weights = [4,10,12], charges = [-9,0,0] Output: [0]
The promotional credit on the first tray outweighs its weight mismatch. The best assignment therefore need not use the tray whose weight is closest to the requested weight.
Constraints
- 0 <= requested.length <= 500
- requested.length <= weights.length <= 2000
- charges.length == weights.length
- 1 <= requested[i], weights[j] <= 1000000
- -1000000 <= charges[j] <= 1000000
The result contains tray indices, not the minimum cost. Negative total costs are allowed. The intended solution uses O(requested.length * weights.length) time and space.
Hints
Show hint 1Hint 1
Let a state describe the minimum cost of assigning the remaining orders using only a suffix of the trays. At each tray, either leave it unused or assign it to the next order.
Show hint 2Hint 2
During reconstruction, prefer assigning the current tray whenever that choice can still achieve the minimum cost. This makes the first selected index, and then each subsequent one, as small as possible.
Follow-up questions
What an interviewer might ask once you have a working solution.
- If only the minimum total cost were required, how could you reduce the auxiliary space?
- How would the recurrence change if every order also specified a maximum allowed weight mismatch?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem