Minimum Space Wasted from Packaging

Problem#

Each package needs a box at least as large as itself. Each supplier provides a set of box sizes; you must pick exactly one supplier. Return the minimum total wasted space (box size minus package size summed over all packages), or -1 if no supplier can fit every package. Result is modulo 10^9 + 7.

Examples#

packages = [2,3,5], boxes = [[4,8],[2,8]] → 6 (supplier 2: 2→2 wastes 0, 3→8 wastes 5, 5→8 wastes 3)
packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]] → -1

Constraints#

1 <= packages.length, boxes.length <= 10^5, 1 <= sum of boxes.length <= 10^5.

Approach#

Sort packages and build a prefix sum. For each supplier, sort their boxes; iterate boxes in order and, via upper_bound, find how many packages still unboxed are at most the current box size. The contribution is boxSize * count - sumOfThosePackages. Skip suppliers whose max box is smaller than the largest package.

Solution#

class Solution {
public:
    int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
        const long MOD = 1'000'000'007;
        sort(packages.begin(), packages.end());
        int n = packages.size();
        vector<long long> pref(n + 1, 0);
        for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + packages[i];
        long long best = LLONG_MAX;
        for (auto& sup : boxes) {
            sort(sup.begin(), sup.end());
            if (sup.back() < packages.back()) continue;
            long long waste = 0;
            int prev = 0;
            for (int b : sup) {
                int idx = upper_bound(packages.begin(), packages.end(), b) - packages.begin();
                if (idx > prev) {
                    waste += (long long)b * (idx - prev) - (pref[idx] - pref[prev]);
                    prev = idx;
                }
            }
            best = min(best, waste);
        }
        if (best == LLONG_MAX) return -1;
        return (int)(best % MOD);
    }
};

func minWastedSpace(packages []int, boxes [][]int) int {
    const MOD int64 = 1_000_000_007
    sort.Ints(packages)
    n := len(packages)
    pref := make([]int64, n+1)
    for i := 0; i < n; i++ {
        pref[i+1] = pref[i] + int64(packages[i])
    }
    var best int64 = math.MaxInt64
    maxPkg := packages[n-1]
    for _, sup := range boxes {
        sort.Ints(sup)
        if sup[len(sup)-1] < maxPkg {
            continue
        }
        var waste int64 = 0
        prev := 0
        for _, b := range sup {
            idx := sort.SearchInts(packages, b+1)
            if idx > prev {
                waste += int64(b)*int64(idx-prev) - (pref[idx] - pref[prev])
                prev = idx
            }
        }
        if waste < best {
            best = waste
        }
    }
    if best == math.MaxInt64 {
        return -1
    }
    return int(best % MOD)
}

import bisect
from typing import List

class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        MOD = 10**9 + 7
        packages.sort()
        n = len(packages)
        pref = [0] * (n + 1)
        for i in range(n):
            pref[i + 1] = pref[i] + packages[i]
        best = float('inf')
        max_pkg = packages[-1]
        for sup in boxes:
            sup.sort()
            if sup[-1] < max_pkg:
                continue
            waste = 0
            prev = 0
            for b in sup:
                idx = bisect.bisect_right(packages, b)
                if idx > prev:
                    waste += b * (idx - prev) - (pref[idx] - pref[prev])
                    prev = idx
            if waste < best:
                best = waste
        if best == float('inf'):
            return -1
        return int(best % MOD)

function minWastedSpace(packages, boxes) {
    const MOD = 1_000_000_007n;
    packages.sort((a, b) => a - b);
    const n = packages.length;
    const pref = new Array(n + 1).fill(0n);
    for (let i = 0; i < n; i++) pref[i + 1] = pref[i] + BigInt(packages[i]);
    const maxPkg = packages[n - 1];
    const upperBound = (target) => {
        let lo = 0, hi = n;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (packages[mid] <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    let best = null;
    for (const sup of boxes) {
        sup.sort((a, b) => a - b);
        if (sup[sup.length - 1] < maxPkg) continue;
        let waste = 0n;
        let prev = 0;
        for (const b of sup) {
            const idx = upperBound(b);
            if (idx > prev) {
                waste += BigInt(b) * BigInt(idx - prev) - (pref[idx] - pref[prev]);
                prev = idx;
            }
        }
        if (best === null || waste < best) best = waste;
    }
    if (best === null) return -1;
    return Number(best % MOD);
}

class Solution {
    public int minWastedSpace(int[] packages, int[][] boxes) {
        final long MOD = 1_000_000_007L;
        Arrays.sort(packages);
        int n = packages.length;
        long[] pref = new long[n + 1];
        for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + packages[i];
        long best = Long.MAX_VALUE;
        int maxPkg = packages[n - 1];
        for (int[] sup : boxes) {
            Arrays.sort(sup);
            if (sup[sup.length - 1] < maxPkg) continue;
            long waste = 0;
            int prev = 0;
            for (int b : sup) {
                int idx = upperBound(packages, b);
                if (idx > prev) {
                    waste += (long) b * (idx - prev) - (pref[idx] - pref[prev]);
                    prev = idx;
                }
            }
            if (waste < best) best = waste;
        }
        if (best == Long.MAX_VALUE) return -1;
        return (int) (best % MOD);
    }

    private int upperBound(int[] a, int target) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

function minWastedSpace(packages: number[], boxes: number[][]): number {
    const MOD = 1_000_000_007n;
    packages.sort((a, b) => a - b);
    const n = packages.length;
    const pref: bigint[] = new Array(n + 1).fill(0n);
    for (let i = 0; i < n; i++) pref[i + 1] = pref[i] + BigInt(packages[i]);
    const maxPkg = packages[n - 1];
    const upperBound = (target: number): number => {
        let lo = 0, hi = n;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (packages[mid] <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    let best: bigint | null = null;
    for (const sup of boxes) {
        sup.sort((a, b) => a - b);
        if (sup[sup.length - 1] < maxPkg) continue;
        let waste = 0n;
        let prev = 0;
        for (const b of sup) {
            const idx = upperBound(b);
            if (idx > prev) {
                waste += BigInt(b) * BigInt(idx - prev) - (pref[idx] - pref[prev]);
                prev = idx;
            }
        }
        if (best === null || waste < best) best = waste;
    }
    if (best === null) return -1;
    return Number(best % MOD);
}

Editorial#

The packages-sorted plus prefix-sum trick converts each “boxes of size at most b waste” sub-question into O(log n). Each supplier processes its boxes in increasing order and “claims” the next slab of packages. Total work across all suppliers is bounded by total boxes, since each box is iterated once.

Complexity#

Time: O((n + sum_b) log n).
Space: O(n).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#