Purchase Optimization
Examples
Example 1:
Input: prices = [3,4,5,5,7], pos = [2,1,5], amount = [10,24,5]
Output: [2,5,0]
Explanation:
Example 2:
Input: prices = [1,2,2,3,6], pos = [3,2,4], amount = [4,7,10]
Output: [1,3,2]
Explanation:
Example 1:
Input: prices = [3,4,5,5,7], pos = [2,1,5], amount = [10,24,5]
Output: [2,5,0]
Explanation:
Example 2:
Input: prices = [1,2,2,3,6], pos = [3,2,4], amount = [4,7,10]
Output: [1,3,2]
Explanation:
Alex is shopping at Ozone Galleria Mall, where cubicles sell products at fixed prices. The cubicles are arranged so that prices is in non-decreasing order.
You are given:
prices, where prices[i] is the price at the (i + 1)th cubiclepos, where pos[i] is Alex's starting cubicle for the ith query (1-indexed)amount, where amount[i] is Alex's budget for the ith queryFor each query, Alex visits cubicles from pos[i] through n moving only to the right. Alex may buy at most one product from each visited cubicle, and the total cost must not exceed amount[i].
Return an array where the ith value is the maximum number of products Alex can buy for the ith query.
For the three queries, Alex can buy at most 2 products from cubicle 2 onward, all 5 products from cubicle 1 onward, and 0 products from cubicle 5 onward.
The cheapest valid suffix purchases are [2], [2,2,3], and [3,6] respectively.
prices.length >= 1pos.length == amount.lengthprices is sorted in non-decreasing order1 <= pos[i] <= prices.length0 <= amount[i]