A distribution center ships liquid medication, and each order requests a specific amount. The center must choose exactly one container set, then fulfill every order using only the capacities available in that set. Each capacity in the chosen set is available in unlimited quantity.
For an order of amount r, the center must use the smallest available capacity c such that . If no capacity in the set is at least r, that set cannot fulfill the order and is invalid. The wasted amount for that order is , so an exact match creates zero waste.
Evaluate every container set and return the 0-based index of the set that can fulfill every order with the minimum total waste. If multiple sets tie, return the smallest index. If no set can fulfill every order, return -1.
The container sets may be supplied in either of two equivalent forms, depending on the environment:
n is the number of orders, requirements is an array of length n, numContainerSets is the number of sets, and containers is a 2D array whose rows are [set_id, capacity]. Rows are grouped by set_id, and capacities within each set are given in nondecreasing order.requirements is an array of order amounts, and containerSets is an array of arrays where containerSets[i] lists the capacities available in set i. Capacities may be unsorted and may contain duplicates.Implement chooseContainers with the signature required by your input format.
Example 1:
Input:
requirements = [2, 8, 5, 10]
containerSets = [[4, 8, 12], [10, 12], [1, 3, 10]]
Output:
0
Explanation: Set 0 wastes 2 + 0 + 3 + 2 = 7, set 1 wastes 8 + 2 + 5 + 0 = 15, and set 2 wastes 1 + 2 + 5 + 0 = 8. The smallest total waste is 7, from set 0.
requirements = [2,8, 5, 10] containerSets = [[4, 8, 12], [10, 12], [1, 3, 10]]
0
Four orders need amounts 2, 8, 5, 10. Three candidate container sets are available.
Example 2:
Input:
requirements = [5, 7, 7]
containerSets = [[8, 5, 8], [7, 10], [4, 6, 9]]
Output:
0
Explanation: Set 0 wastes 0 + 1 + 1 = 2, set 1 wastes 2 + 0 + 0 = 2, and set 2 wastes 1 + 2 + 2 = 5. Sets 0 and 1 tie at 2, so the smaller index 0 is returned.
Example 3:
Input:
requirements = [100]
containerSets = [[40, 50], [25, 75]]
Output:
-1
Explanation: Neither set contains a capacity of at least 100, so no set can fulfill the order.
Constraints:
requirements = [2,8, 5, 10] containerSets = [[4, 8, 12], [10, 12], [1, 3, 10]]
0
Four orders need amounts 2, 8, 5, 10. Three candidate container sets are available.