Problem statement

https://leetcode.com/problems/minimum-space-wasted-from-packaging/

Solution

Let us consider some example and it will become clearer what to do here. Imagine packages = [3, 5, 8, 10, 11, 12] and boxes[0] = [5, 10, 13, 14]. Then what we need to do is to separate packages like this:

3 5 | 8 10 | 11 12 ||

Here by vertical lines I put the biggest package which we can pack in box: 3, 5 can be packed in box with size 5, 3, 5, 8, 10 in box with size 10 and so on. Notice that we have two bars in the end, because all boxes can be packed in 13 and 14. What we need to do is to sort these places and then put each group in corresponding box. Notice that I added dummy variable in the beginning. To evaluate number of waste in group we multiply number of elements (pl2 - pl1) in this group by box size el2 and subtract all boxes which are in this group (in fact, we can avoid to subtract, because in the end we subtract all boxes).

Finally, we need to do this for each supplier B in boxes.

Complexity

Let k = sum(len(boxes)), by constraints it is <= 10^5. Let n = len(packages). Then we have time complexity O(n * log n + k * log k + k*log n). Space complexity is O(n + k).

Code

from bisect import bisect

class Solution:
    def minWastedSpace(self, packages, boxes):
        P = sorted(packages)
        acc, ans = [0] + list(accumulate(P)), inf
        for B in boxes:
            places = [(0, 0)] + sorted([(bisect(P, x), x) for x in B])
            if places[-1][0] < len(P): continue
            
            wasted = 0
            for i in range(len(B)):
                pl1, el1 = places[i]
                pl2, el2 = places[i+1]
                wasted += (pl2 - pl1)*el2 - (acc[pl2] - acc[pl1])
                
            ans = min(ans, wasted)
            
        return ans % (10**9 + 7) if ans != inf else -1