{x}
blog image

Minimum Space Wasted From Packaging

You have n packages that you are trying to place in boxes, one package in each box. There are m suppliers that each produce boxes of different sizes (with infinite supply). A package can be placed in a box if the size of the package is less than or equal to the size of the box.

The package sizes are given as an integer array packages, where packages[i] is the size of the ith package. The suppliers are given as a 2D integer array boxes, where boxes[j] is an array of box sizes that the jth supplier produces.

You want to choose a single supplier and use boxes from them such that the total wasted space is minimized. For each package in a box, we define the space wasted to be size of the box - size of the package. The total wasted space is the sum of the space wasted in all the boxes.

  • For example, if you have to fit packages with sizes [2,3,5] and the supplier offers boxes of sizes [4,8], you can fit the packages of size-2 and size-3 into two boxes of size-4 and the package with size-5 into a box of size-8. This would result in a waste of (4-2) + (4-3) + (8-5) = 6.

Return the minimum total wasted space by choosing the box supplier optimally, or -1 if it is impossible to fit all the packages inside boxes. Since the answer may be large, return it modulo 109 + 7.

 

Example 1:

Input: packages = [2,3,5], boxes = [[4,8],[2,8]]
Output: 6
Explanation: It is optimal to choose the first supplier, using two size-4 boxes and one size-8 box.
The total waste is (4-2) + (4-3) + (8-5) = 6.

Example 2:

Input: packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
Output: -1
Explanation: There is no box that the package of size 5 can fit in.

Example 3:

Input: packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
Output: 9
Explanation: It is optimal to choose the third supplier, using two size-5 boxes, two size-10 boxes, and two size-14 boxes.
The total waste is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9.

 

Constraints:

  • n == packages.length
  • m == boxes.length
  • 1 <= n <= 105
  • 1 <= m <= 105
  • 1 <= packages[i] <= 105
  • 1 <= boxes[j].length <= 105
  • 1 <= boxes[j][k] <= 105
  • sum(boxes[j].length) <= 105
  • The elements in boxes[j] are distinct.

Problem Description

The problem asks to find the minimum wasted space when packaging a set of packages into boxes supplied by different suppliers. Each supplier provides boxes of various sizes. A package can only be placed in a box if the package size is less than or equal to the box size. The goal is to select a supplier and assign packages to boxes such that the total wasted space (sum of (box size - package size) for all packages) is minimized. If it's impossible to fit all packages, return -1.

Approach

The solution uses a combination of sorting and binary search for efficient processing.

  1. Sort: Sort the packages array in ascending order. This allows for efficient binary search later.

  2. Iterate Through Suppliers: For each supplier's boxes, sort the boxes array as well.

  3. Check Feasibility: Before processing a supplier's boxes, verify if it's even possible to fit all packages. This is done by checking if the largest package size is less than or equal to the largest box size offered by the supplier. If not, skip the supplier.

  4. Assign Packages and Calculate Waste: This is the core of the algorithm. We iterate through the sorted boxes. For each box size b, we use binary search (bisect_right in Python, upper_bound in C++, sort.SearchInts in Go, search in Java and Typescript) to find the index j in the packages array such that all packages from index i up to j (exclusive) have sizes less than or equal to b. We then calculate the wasted space for this box as (j-i) * b. We update i to j to proceed to the next box.

  5. Minimize Wasted Space: Keep track of the minimum wasted space (ans) across all suppliers.

  6. Return Result: After checking all suppliers, if no supplier could accommodate all packages (ans remains infinity), return -1. Otherwise, subtract the total package size from the minimum wasted space and return the result modulo 109 + 7.

Time and Space Complexity Analysis

  • Time Complexity: O(N log N + M log M + N log B), where N is the number of packages, M is the number of suppliers, and B is the total number of boxes across all suppliers. The dominant factors are sorting the packages and boxes (O(N log N) and O(M log M) at worst) and the nested loop with binary search (O(N log B)).

  • Space Complexity: O(1) auxiliary space. The sorting is done in place, and only a few variables are used to store intermediate results.

Code Implementation (Python3)

import bisect
from typing import List
 
class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        mod = 10**9 + 7
        ans = float('inf')
        packages.sort()
        for box in boxes:
            box.sort()
            if packages[-1] > box[-1]:
                continue
            s = i = 0
            for b in box:
                j = bisect_right(packages, b, lo=i)
                s += (j - i) * b
                i = j
            ans = min(ans, s)
        if ans == float('inf'):
            return -1
        return (ans - sum(packages)) % mod

The code in other languages (Java, C++, Go, TypeScript) follows a similar structure, adapting the sorting and binary search functions according to the language's specific libraries. The core logic of iterating through suppliers, checking feasibility, assigning packages, and calculating the minimum wasted space remains consistent across all implementations.