Most Items From a Start Index
HardArrays ยท HRT
Given an integer array prices and a list queries, where each query is [start, budget], return a list with one answer per query: the largest number of items you can buy using only indices start and above, with total price at most budget.
Each index can be bought at most once, and queries are independent of each other.
Example 1
- Input:
- prices = [4, 2, 7, 1, 3], queries = [[0, 6], [2, 8], [3, 2], [4, 2]]
- Output:
- [3, 2, 1, 0]
- Explanation
- For
[0, 6]the cheapest three prices cost 1 + 2 + 3 = 6, and a fourth item would exceed the budget.
Example 2
- Input:
- prices = [5, 5, 5], queries = [[0, 10], [1, 4], [2, 5]]
- Output:
- [2, 0, 1]
Example 3
- Input:
- prices = [0, 3, 0, 2], queries = [[1, 2], [0, 0]]
- Output:
- [2, 2]
- Explanation
- Free items cost nothing, so a budget of 0 still buys both of them.
Constraints
1 <= prices.length <= 1000000 <= prices[i] <= 10^91 <= queries.length <= 1000000 <= start < prices.length0 <= budget <= 10^15