Problem: Optimal Container Set Selection

You are tasked with packaging medicine for shipment and must select exactly one container set to fulfill all customer orders. Once a set is chosen, you can only use containers from that specific set.

Each container set provides containers of defined capacities in unlimited quantity. For every customer order, you must adhere to the following rules:

1. Use exactly one container from the chosen set.
2. Completely fill the container up to the order amount.
3. If no container has a 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 defined as waste for that specific order.

If, for any single order, no container in a chosen set is large enough to accommodate the order_amount, then that container set is considered invalid and cannot be used at all.

Your objective is to evaluate all available container sets and identify the one that:

• Can satisfy all customer orders (meaning for every requirement, there is at least one container in the set with capacity ≥ requirement).
• Results in the minimum total waste, where total waste is the sum of wasted units across all orders.

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

Input Format

YouYou will be provided with:

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

Additional Guarantees for containers:

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

Constraints:

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 specific container set s with capacities C_s and 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.

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

Required Function

Implement the following function:

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 must be efficient enough to handle inputs up to 10^5 in size; a naive solution with O(n × totalNumContainers) time complexity 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}:
  • Requirement 4 → use capacity 5 → waste = 5 − 4 = 1
  • Requirement 6 → use capacity 7 → waste = 7 − 6 = 1
  • Requirement 6 → use capacity 7 → waste = 1
  • Requirement 7 → use capacity 7 → waste = 0
  • Total waste for set 0: 1 + 1 + 1 + 0 = 3.
• Set 1 with capacities {6, 8, 9}:
  • Requirement 4 → use capacity 6 → waste = 6 − 4 = 2
  • Requirement 6 → use capacity 6 → waste = 0
  • Requirement 6 → use capacity 6 → waste = 0
  • 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, as its maximum capacity is 6 < 7.
  • Therefore, set 2 is invalid.

Both set 0 and set 1 are valid and yield a total waste of 3. As the smallest index is required, the correct answer is 0.