Maximum Products by Budget
Learn this problem
MicrosoftINTERNOAProblem statement
Alex is shopping at Ozone Galleria Mall, where each cubicle sells products at a fixed price. The cubicles are arranged from left to right in non-decreasing order of price.
You are given an array of n integers, prices, where prices[i] is the price at the ith cubicle, and a list of queries. Each query contains:
pos: Alex's 1-based initial positionamount: the amount of money Alex has
For each query, Alex visits every cubicle from position pos through n. He may buy at most one product from each visited cubicle. Return the maximum number of products he can buy without spending more than amount.
Function
maximumProducts(prices: int[], queries: int[][]) → int[]Examples
Example 1
prices = [3,4,5,5,7]queries = [[2,10],[1,24],[5,5]]return = [2,5,0]pos = 2,amount = 10: Alex visits cubicles 2 through 5 and can buy at most 2 products. He can choose any of the following pairs:- Cubicles 2 and 3:
4 + 5 = 9(<= 10) - Cubicles 2 and 4:
4 + 5 = 9(<= 10) - Cubicles 3 and 4:
5 + 5 = 10(<= 10)
The answer is
2.- Cubicles 2 and 3:
pos = 1,amount = 24: Alex visits all cubicles and can buy from all of them because the total cost is3 + 4 + 5 + 5 + 7 = 24(<= 24).The answer is
5.pos = 5,amount = 5: Alex can visit only cubicle 5, but cannot buy its product because the price7exceeds the available amount5.The answer is
0.