Container Group Minimum Waste
HardBinary Search ยท IMC
Given orders, the sizes of the items to ship, and groups, where groups[g] lists the capacities of the container types in group g, choose exactly one group. Any number of containers of each type is available. Each order goes into the container type in the chosen group with the smallest capacity that is at least the order's size, and wastes capacity minus size.
Return the minimum total waste over all groups that can hold every order, or -1 if no group can.
Example 1
- Input:
- orders = [4, 7, 2], groups = [[5, 8], [3, 7, 9], [10], [6, 6]]
- Output:
- 4
- Explanation
- Group 1 puts 4 in 7, 7 in 7 and 2 in 3, wasting 3 + 0 + 1. Group 3 cannot hold the 7.
Example 2
- Input:
- orders = [12, 3], groups = [[10, 11], [5]]
- Output:
- -1
Example 3
- Input:
- orders = [5, 5, 5], groups = [[9, 5, 5], [6]]
- Output:
- 0
- Explanation
- Capacity 5 fits each order exactly, and containers can be reused.
Constraints
1 <= orders.length <= 10^51 <= groups.length <= 10^3, and eachgroups[g]has at least one capacity1 <= orders[i], groups[g][j] <= 10^9- The total number of capacities across all groups is at most
10^5