Minimum Space Wasted From Packaging - Leetcode Solution

The Minimum Space Wasted From Packaging problem on LeetCode asks us to determine the minimum amount of wasted space when packing items into packages with different sizes.

Here's a detailed solution to the problem:

1. First, we need to sort the items in non-decreasing order according to their sizes.

2. Next, we need to iterate through all the packages and determine which items can be packed into each package. To do this efficiently, we can maintain a pointer to the current item that we are considering packing and a variable to keep track of the total space used so far in the current package.

3. For each package, we need to iterate through the items and add as many items as possible to the package without exceeding its size. If we encounter an item that would cause the package to exceed its size, we move on to the next package and repeat the process.

4. Once we have packed all the items into the packages, we can calculate the wasted space by subtracting the total space used by the items from the total space available in the packages.

The time complexity of this solution is O(n log n), where n is the number of items, due to the sorting step. The space complexity is O(1), since we are not using any extra data structures apart from the input arrays.

Here's the Python code for the solution:

class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        packages.sort()
        min_wasted_space = float('inf')
        
        for box in boxes:
            box.sort()
            i, j = 0, 0
            wasted_space = 0
            
            while i < len(packages) and j < len(box):
                if packages[i] <= box[j]:
                    wasted_space += box[j] - packages[i]
                    i += 1
                else:
                    j += 1
            
            if i == len(packages):
                min_wasted_space = min(min_wasted_space, wasted_space)
        
        return -1 if min_wasted_space == float('inf') else min_wasted_space % (10**9 + 7)

1