<p>You have <code>n</code> packages that you are trying to place in boxes, <strong>one package in each box</strong>. There are <code>m</code> suppliers that each produce boxes of <strong>different sizes</strong> (with infinite supply). A package can be placed in a box if the size of the package is <strong>less than or equal to</strong> the size of the box.</p>

<p>The package sizes are given as an integer array <code>packages</code>, where <code>packages[i]</code> is the <strong>size</strong> of the <code>i<sup>th</sup></code> package. The suppliers are given as a 2D integer array <code>boxes</code>, where <code>boxes[j]</code> is an array of <strong>box sizes</strong> that the <code>j<sup>th</sup></code> supplier produces.</p>

<p>You want to choose a <strong>single supplier</strong> and use boxes from them such that the <strong>total wasted space </strong>is <strong>minimized</strong>. For each package in a box, we define the space <strong>wasted</strong> to be <code>size of the box - size of the package</code>. The <strong>total wasted space</strong> is the sum of the space wasted in <strong>all</strong> the boxes.</p>

<ul>
	<li>For example, if you have to fit packages with sizes <code>[2,3,5]</code> and the supplier offers boxes of sizes <code>[4,8]</code>, you can fit the packages of size-<code>2</code> and size-<code>3</code> into two boxes of size-<code>4</code> and the package with size-<code>5</code> into a box of size-<code>8</code>. This would result in a waste of <code>(4-2) + (4-3) + (8-5) = 6</code>.</li>
</ul>

<p>Return <em>the <strong>minimum total wasted space</strong> by choosing the box supplier <strong>optimally</strong>, or </em><code>-1</code> <i>if it is <strong>impossible</strong> to fit all the packages inside boxes. </i>Since the answer may be <strong>large</strong>, return it <strong>modulo </strong><code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> packages = [2,3,5], boxes = [[4,8],[2,8]]
<strong>Output:</strong> 6
<strong>Explanation</strong>: It is optimal to choose the first supplier, using two size-4 boxes and one size-8 box.
The total waste is (4-2) + (4-3) + (8-5) = 6.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There is no box that the package of size 5 can fit in.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
<strong>Output:</strong> 9
<strong>Explanation:</strong> It is optimal to choose the third supplier, using two size-5 boxes, two size-10 boxes, and two size-14 boxes.
The total waste is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == packages.length</code></li>
	<li><code>m == boxes.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= packages[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= boxes[j].length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= boxes[j][k] &lt;= 10<sup>5</sup></code></li>
	<li><code>sum(boxes[j].length) &lt;= 10<sup>5</sup></code></li>
	<li>The elements in <code>boxes[j]</code> are <strong>distinct</strong>.</li>
</ul>

class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int :
        # n packages in n boxes 
        # m packagers who produce boxes of different sizes 
        # need -> range of boxes produceable map to producers who produce them 
        # box most be greater than or equal to package size 
        # packages -> size of the ith package 
        # boxes    -> ith supplier 
        #           |
        #           v
        #           jth sizes available 
        # goal is to find best singular box list such that 
            # all packages are done 
            # minimal waste is produced 
        # ideas 
        # sort packages -> largest size is limiting factor 
        # sort boxes at each supplier -> if largest size is not largest package useable
            # remove from consideration 
        # if after removing from consideration, none remain -> return -1 
        # final answer may be large -> use modulo 
        # packages can be reduced to frequency packages 
        # counter conversion 
        packages, package_sum = collections.Counter(packages), sum(packages)
        # get max package and min package 
        max_package, min_package = max(packages.keys()), min(packages.keys())
        # only care about the useable ones 
        new_box_list = []
        for box_list in boxes : 
            box_list.sort()
            if box_list[-1] >= max_package : 
                # find actual final index of the max package in box list 
                final_index = bisect.bisect_right(box_list, max_package)
                # find actual first index of the min package in box list
                first_index = bisect.bisect_left(box_list, min_package)
                # go only up to there inclusive 
                new_box_list.append(box_list[first_index:final_index+1])
            else : 
                continue 

        # but if there are not any, we can quit early 
        if len(new_box_list) == 0 : 
            return -1

        # otherwise, we must solve, so set up mod 
        mod = 10**9 + 7
        # Then we now build our prefix sum
        prefix_sum = [0] * (max_package + 1)
        for package in packages : 
            prefix_sum[package] = packages[package]

        # loop over prefix sum of frequencies to make proper prefix sum 
        for index in range(min_package, max_package+1) : 
            prefix_sum[index] += prefix_sum[index - 1]

        # set up wasted space 
        wasted_space = math.inf
        # for box list in new box list 
        for box_list in new_box_list :
            # get current waste as negative package sum 
            current_waste  = -package_sum 
            # set up previous box as box 0 
            previous_box = 0 
            # set count to start 
            count = 0 
            # loop over boxes by index to stop index 
            for current_box in box_list :
                # if this box is too big all others will be as well  
                if current_box >= max_package : 
                    # set count variable prefix sum at max packages - prefix sum of previous box 
                    count = prefix_sum[max_package] - prefix_sum[previous_box]
                    # increase current waste by count * current box as that is the amount of waste generated here
                    current_waste += count * current_box
                    break
                else : 
                    # otherwise count is the prefix sum at current minus previous
                    count = prefix_sum[current_box] - prefix_sum[previous_box]
                    # and the waste goes up by count times current box (waste for using this box)
                    current_waste += count * current_box 
                    # and the previous box updates appropriately 
                    previous_box = current_box 
            # at end update wasted space as needed 
            wasted_space = min(wasted_space, current_waste)
        # answer is gauranteed due to earlier work 
        return wasted_space % mod
1106