Maximize Item Counts Under Suffix Budget Queries

Problem Statement

You are given an array of positive integers prices, where prices[i] represents the price of the i-th item in a shop.

You are also given a list of queries queries, where each query is a pair [start_i, budget_i]. For each query:

• You may only purchase items at indices j such that j >= start_i.
• You can choose any subset of eligible items (they do not need to be consecutive).
• Each eligible item can be purchased at most once.
• The total sum of chosen item prices cannot exceed budget_i.

Return an array of integers representing the maximum number of items you can purchase for each query. Queries are completely independent of one another.

Function Signature

def max_items_purchased(prices: list[int], queries: list[list[int]]) -> list[int]:
    pass

Input & Output Format

• Input:
  • prices: A list of positive integers.
  • queries: A 2D list of integers where queries[k] = [start_k, budget_k].
• Output:
  • A list of integers where the k-th integer is the answer to queries[k].

Constraints

• 1 <= len(prices) <= 1000
• 1 <= len(queries) <= 1000
• 0 <= start_i < len(prices)
• 1 <= prices[i] <= 10^9
• 1 <= budget_i <= 10^14

Examples

Example 1

Input: prices = [5, 2, 8, 1, 3], queries = [[0, 7], [2, 4], [3, 10]]
Output: [3, 2, 2]

Explanation:

• Query 0: start = 0, budget = 7. Eligible items are [5, 2, 8, 1, 3]. Sorting by cost gives [1, 2, 3, 5, 8]. Picking items with prices 1, 2, 3 costs 6 7). Maximum items = 3.
• Query 1: start = 2, budget = 4. Eligible items are [8, 1, 3]. Sorted: [1, 3, 8]. Picking 1 and 3 costs 4 <= 4. Maximum items = 2.
• Query 2: start = 3, budget = 10. Eligible items are [1, 3]. Both items cost 4 <= 10. Maximum items = 2.

Example 2

Input: prices = [10, 20, 30], queries = [[1, 5], [0, 60]]
Output: [0, 3]

Explanation:

• Query 0: start = 1, budget = 5. The cheapest eligible item costs 20, which is greater than 5. Maximum items = 0.
• Query 1: start = 0, budget = 60. Sum of all items is 10 + 20 + 30 = 60 <= 60. Maximum items = 3.