Minimum Space Wasted From Packaging LeetCode solution in Python

1
# Runtime: 2545 ms (Top 38.89%) | Memory: 37.8 MB (Top 95.24%)
2
class Solution:
3
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
4
        # prefix sum to save time
5
        acc = [0] + [*accumulate(packages)]
6
        packages.sort()
7

8
        ans = float("inf")
9
        for box in boxes:
10
            tmp = 0
11
            # deal with smallest box first
12
            box.sort()
13

14
            # record number of packages already dealt with
15
            start = 0
16

17
            for b in box:
18
                loc = bisect.bisect(packages, b)
19
                if loc == 0:
20
                    continue
21
                tmp += b * (loc - start) - (acc[loc] - acc[start])
22

23
                # all are packaged
24
                if loc == len(packages):
25
                    ans = min(ans, tmp)
26
                    break
27

28
                start = loc
29

30
        return ans % (10**9 + 7) if ans != float("inf") else -1