Choose container set to minimize waste

You are packaging medicine for shipment. You can choose exactly one container set and then must use containers only from that set to fulfill all customer orders.

Each container set defines the capacities of containers that are available in unlimited quantity. For a given order, you must:

1. Use exactly one container from the chosen set.
2. Completely fill the container up to the order amount.
3. If there is no container with capacity exactly equal to the order amount, you must use the smallest container whose capacity is greater than the order amount.
4. The difference capacity - order_amount is considered waste for that order.

If, for some order, no container in a set is large enough, then that set cannot be used at all.

Your task is to evaluate all container sets and choose the one that:

• Can satisfy all orders (every requirement has at least one container in that set with capacity ≥ requirement), and
• Has the minimum total waste , where total waste is the sum of wasted units over all orders.

If multiple container sets yield the same minimum total waste, return the smallest index among them. If no container set can satisfy all the orders, return -1.

Input format

You are given:

• An integer n : the number of orders.
• An array requirements[n] : positive integers where requirements[i] is the required volume for the i -th order.
• An integer numContainerSets : the number of distinct container sets.
• A 2D array containers[totalNumContainers][2] describing all container sizes across all sets, where:
  • containers[k][0] is the set index (an integer from 0 to numContainerSets - 1 ),
  • containers[k][1] is a container capacity (a positive integer) belonging to that set.

Additional guarantees about containers:

• Rows are grouped by set index in increasing order of the index.
• Within each set, its capacities are listed in non-decreasing order.

You may assume reasonable constraints such as:

• 1 ≤ n ≤ 10^5
• 1 ≤ numContainerSets ≤ 10^5
• 1 ≤ totalNumContainers ≤ 10^5
• 1 ≤ requirements[i] ≤ 10^9
• 1 ≤ containers[k][1] ≤ 10^9

Waste calculation for a single set

For a fixed container set s with capacities C_s and for an order of size r:

• Let c be the smallest capacity in C_s such that c ≥ r .
• The waste for this order under set s is c - r .
• If no such c exists (i.e., all capacities in C_s are < r ), then set s is invalid and cannot be used at all.

The total waste for set s is the sum of wastes over all orders in requirements.

Required function

Implement the following function (in any language):

int chooseContainers(int requirements[n],
                     int numContainerSets,
                     int containers[totalNumContainers][2])

Return value:

• The 0-based index of the container set that yields the minimum total waste while satisfying all requirements; if multiple such sets exist, return the smallest index among them.
• If no container set can satisfy all requirements, return -1 .

Your algorithm should be efficient enough to handle inputs up to 10^5 in size; a naive solution that is $O(n \times \text{totalNumContainers})$ or worse will time out.

Example

n = 4
requirements = [4, 6, 6, 7]
numContainerSets = 3
containers = [
  [0, 3], [0, 5], [0, 7],  // set 0: capacities {3, 5, 7}
  [1, 6], [1, 8], [1, 9],  // set 1: capacities {6, 8, 9}
  [2, 3], [2, 5], [2, 6]   // set 2: capacities {3, 5, 6}
]

• Set 0 with capacities {3, 5, 7} :
  • For requirement 4 → use capacity 5 → waste = 5 − 4 = 1
  • For requirement 6 → use capacity 7 → waste = 7 − 6 = 1
  • For requirement 6 → use capacity 7 → waste = 1
  • For requirement 7 → use capacity 7 → waste = 0
  • Total waste for set 0: 1 + 1 + 1 + 0 = 3 .
• Set 1 with capacities {6, 8, 9} :
  • For requirement 4 → use capacity 6 → waste = 6 − 4 = 2
  • For requirement 6 → use capacity 6 → waste = 0
  • For requirement 6 → use capacity 6 → waste = 0
  • For requirement 7 → use capacity 8 → waste = 8 − 7 = 1
  • Total waste for set 1: 2 + 0 + 0 + 1 = 3 .
• Set 2 with capacities {3, 5, 6} :
  • Cannot satisfy requirement 7, since its maximum capacity is 6 < 7.
  • Therefore set 2 is invalid .

Both set 0 and set 1 are valid and yield total waste 3. Since we must return the smallest index among those, the correct answer is:

chooseContainers(...) = 0