Choose container set to minimize waste

Question

A pharmaceutical company is packaging liquid medicine for shipment. Each customer order has a required volume. The company can choose exactly one "container set" and must then fulfill all orders using containers only from that chosen set.

Each container set defines the capacities of containers available in unlimited quantity. For each order you must:

1. Use exactly one container from the chosen set.
2. Fill that container completely up to the order amount.
3. If a container with capacity exactly equal to the order amount exists, use it (waste = 0). Otherwise, use the smallest container whose capacity is greater than the order amount.
4. The waste for an order is capacity - order_amount.

If, for some order, no container in a set is large enough (no capacity >= requirement), then that set is invalid and cannot be used at all.

Evaluate every container set and choose the one that:

• Can satisfy all orders, and
• Has the minimum total waste, where total waste is the sum of wasted units over all orders.

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

Input format

The required input is provided to you in one of two equivalent forms (handle whichever your harness gives):

Form A — flat 2D array grouped by set:

• 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], where containers[k][0] is the set index (0 to numContainerSets - 1) and containers[k][1] is a container capacity (positive integer) belonging to that set.
• Rows are grouped by set index in increasing order of index.
• Within each set, capacities are listed in non-decreasing order.

Form B — list of capacity arrays:

• requirements[] (length m): the volume required for each order.
• containerSets: a list where containerSets[i] is an array of the container capacities available in set i. Capacities may appear in any order and duplicates may exist.

Constraints

• 1 <= n <= 10^5
• 1 <= numContainerSets <= 10^5
• 1 <= totalNumContainers <= 2 * 10^5
• 1 <= requirements[i] <= 10^9
• 1 <= capacity <= 10^9

Your algorithm must be efficient enough to handle inputs at the upper bounds. A naive solution that is O(n * totalNumContainers) or worse will time out.

Required function

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

Return value:

• The 0-based index of the container set with the minimum total waste that satisfies all requirements (smallest index on ties), or
• -1 if no container set can satisfy all requirements.

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 {3, 5, 7}: 4->5 (waste 1), 6->7 (1), 6->7 (1), 7->7 (0) => total 3.
• Set 1 {6, 8, 9}: 4->6 (waste 2), 6->6 (0), 6->6 (0), 7->8 (1) => total 3.
• Set 2 {3, 5, 6}: cannot satisfy requirement 7 (max capacity 6 < 7) => invalid.

Set 0 and Set 1 both achieve the minimum total waste of 3, so return the smaller index:

chooseContainers(...) = 0