Solution: Minimum Space Wasted From Packaging

Statement

You have n packages that need to be placed into boxes, with one package per box. There are m suppliers, and each supplier offers boxes of different sizes (with an infinite supply of each size). A package can only fit into a box if the size of the box is greater than or equal to the size of the package.

The sizes of the packages and boxes are provided as follows:

• The sizes of the packages are given as an integer array, packages, where packages[i] represents the size of the i-th package.

• The sizes of the boxes offered by the j-th supplier are given in a 2D array, boxes, where boxes[j] is an array of distinct box sizes provided by that supplier.

You want to choose a single supplier and use boxes from them to minimize wasted space. The wasted space for a package is calculated as the difference between the box and package sizes. The total wasted space is the sum of the wasted space for all the packages.

Return the minimum wasted space by selecting the supplier whose boxes result in the least waste, or return $-1$ if it is impossible to fit all the packages using any supplier’s boxes. As the result can be large, return it modulo $10^9+7$.

Constraints:

• n == packages.length, m == boxes.length

• $1 \leq$ n, m $\leq 50$

• $1 \leq$ packages[i] $\leq 10^3$

• $1 \leq$ boxes[j].length $\leq 30$

• sum(boxes[j].length) $\leq 10^5$

• $1 \leq$ boxes[j][k] $\leq 10^3$

• The elements in boxes[j] are distinct.

Solution

The algorithm computes the minimum space wasted when fitting packages into boxes provided by suppliers. It begins by sorting the packages array, allowing efficient range computation for each box size using binary search. For each supplier, the sizes of their boxes are also sorted, and the algorithm then checks whether the largest box of the supplier can accommodate the largest package. This is done by comparing the largest box size (the last element in the sorted list of box sizes) with the largest package size (the last element in the sorted list of package sizes). If the largest box size is smaller than the largest package size, the supplier is skipped as they cannot accommodate all the packages.

Once the packages and boxes are sorted, the algorithm uses binary search to efficiently find the first package that cannot fit into each box. Specifically, for each box, the binary search locates the smallest package that exceeds the box size. This helps determine how many packages can fit into the box by identifying the range of packages smaller than or equal to the current box size. The binary search works by repeatedly halving the search space until the index of the first package that exceeds the box size is found, allowing the algorithm to quickly determine the fitting packages for that box. The total space used for the box is then calculated by multiplying the box size by the number of packages that fit into the box. The waste for a supplier is calculated as the difference between the total space used for their boxes and the total size of the packages. The algorithm tracks the minimum waste across all suppliers. If no supplier’s boxes can fit all the packages, the result is −1. Otherwise, the result is returned modulo $10^9 + 7$ to handle large numbers.

The steps of the algorithm are as follows:

1. The packages array is sorted to enable efficient binary search for determining which packages fit into each box.

2. Calculate the total size of all packages (totalPackageSize), which helps calculate each supplier’s total wasted space. Initialize minWaste to infinity (float('inf')) to track the smallest waste across all suppliers.

3. Iterate over each supplier:

   1. For each supplier, sort their boxSizes. Sorting is necessary to determine the package range that fits in each box.

   2. Skip suppliers whose largest box cannot fit the largest package (boxSizes[boxSizes.length - 1] < packages[packages.length - 1]). If boxSizes[boxSizes.length - 1] (the largest box) is smaller than packages[packages.length - 1] (the largest package), it means that the largest package cannot fit in any of the boxes from this supplier. Therefore, the supplier is skipped, and the algorithm moves to the next supplier.

   3. Calculate waste for a supplier:

      1. For each valid supplier, initialize totalSpaceUsed to 0 and startIndex to 0, indicating the beginning of the unprocessed packages.

      2. Iterate over the sorted boxSizes:

         1. Use the binarySearch helper function to find the endIndex, which is the index of the first package that does not fit into the current box (boxSize). The binarySearch function finds the smallest element in packages greater than the current boxSize, starting from startIndex.

         2. The number of packages that can fit into the current box is numPackages = endIndex - startIndex. The total space used by these packages is boxSize * numPackages, which is added to totalSpaceUsed.

         3. Update startIndex to endIndex to process remaining packages.

      3. After processing all the boxes for a supplier, subtract totalPackageSize from totalSpaceUsed to calculate the current supplier’s waste and update minWaste if the current supplier’s waste is smaller than minWaste.

4. If no supplier could fit all packages (minWaste is still infinity), return -1. Otherwise, calculate the minimized waste as (minWaste - totalPackageSize)% $(10^9+7)$ to handle large numbers.

Let’s look at the following illustration to get a better understanding of the solution: