We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Space Wasted From Packaging

Number: 2018

Difficulty: Hard

Paid? No

Companies: Two Sigma, Amazon

Problem Description

Given an array of package sizes and multiple suppliers each providing boxes of various sizes, you are required to pack each package into a box (one package per box). A package can only fit into a box if its size is less than or equal to the box’s size. For each package in a box the wasted space is (box size - package size). You must choose a single supplier and minimize the total wasted space. If it is impossible to fit all packages using one supplier’s boxes, return -1. Since the answer may be large, return it modulo 10^9 + 7.

Key Insights

  • Sort the package sizes to enable efficient grouping.
  • Compute a prefix sum on the sorted packages to quickly calculate the sum of values in any interval.
  • For each supplier, sort their list of box sizes.
  • Use binary search to identify the range of packages that can fit into a given box size.
  • Accumulate wasted space by choosing for each box size the maximum possible packages that can be packed without overlaps.
  • Track the minimum wasted space across all suppliers that can cover every package.

Space and Time Complexity

Time Complexity: O(n log n + Σ(boxes_j log n)) where n is the number of packages and the sum is taken over all suppliers’ boxes. Space Complexity: O(n) for sorting the packages and computing the prefix sum.

Solution

The solution begins by sorting the array of packages and computing its prefix sum to efficiently calculate the total package sizes in any interval. For each supplier, sort their available box sizes. Then, for each box size offered by the supplier, greedily pack as many of the remaining packages as possible using binary search to find the furthest package that fits. For every subset of packages assigned to a box size, the wasted space is computed as (number of packages in the group) multiplied by the box size minus the sum of the package sizes in that group. If at the end a supplier is found that can pack all packages, update the global minimum wasted space, otherwise ignore that supplier. Finally, return the minimum waste modulo 10^9 + 7, or -1 if no supplier can pack all packages.

Code Solutions

# Python solution for Minimum Space Wasted From Packaging

import bisect

MOD = 10**9 + 7

def minWastedSpace(packages, boxes):
    packages.sort()  # Sort the packages for binary search
    n = len(packages)
    # Compute prefix sum for quick interval sum queries
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + packages[i]
    
    min_waste = float('inf')
    
    # Evaluate each supplier
    for supplier in boxes:
        supplier.sort()  # Sort the supplier's boxes
        # If the largest box cannot fit the largest package, skip this supplier
        if supplier[-1] < packages[-1]:
            continue
        
        waste = 0
        prev_index = 0
        # Use each box size to cover as many packages as possible
        for box in supplier:
            # Find the rightmost index where the package can fit in the box
            # bisect_right returns index of first element greater than box
            index = bisect.bisect_right(packages, box, lo=prev_index)
            if index > prev_index:
                # Calculate number of packages assigned to this box size
                count = index - prev_index
                # Total space used if all these packages use a box of size "box"
                total_box_space = count * box
                # Actual sum of package sizes from prev_index to index-1
                total_packages = prefix[index] - prefix[prev_index]
                waste += (total_box_space - total_packages)
                prev_index = index
            # If all packages are assigned, exit early
            if prev_index == n:
                break
        
        min_waste = min(min_waste, waste)
    
    return min_waste % MOD if min_waste != float('inf') else -1

# Example usage:
print(minWastedSpace([2,3,5], [[4,8],[2,8]]))  # Output: 6
← Back to All Questions