Formatted question description: https://leetcode.ca/all/1889.html

# 1889. Minimum Space Wasted From Packaging

## Level

Hard

## Description

You have `n`

packages that you are trying to place in boxes, **one package in each box**. There are `m`

suppliers that each produce boxes of **different sizes** (with infinite supply). A package can be placed in a box if the size of the package is **less than or equal to** the size of the box.

The package sizes are given as an integer array `packages`

, where `packages[i]`

is the **size** of the `i-th`

package. The suppliers are given as a 2D integer array `boxes`

, where `boxes[j]`

is an array of **box sizes** that the `j-th`

supplier produces.

You want to choose a **single supplier** and use boxes from them such that the **total wasted space** is **minimized**. For each package in a box, we define the space **wasted** to be `size of the box - size of the package`

. The **total wasted space** is the sum of the space wasted in **all** the boxes.

- For example, if you have to fit packages with sizes
`[2,3,5]`

and the supplier offers boxes of sizes`[4,8]`

, you can fit the packages of size-`2`

and size-`3`

into two boxes of size-`4`

and the package with size-`5`

into a box of size-`8`

. This would result in a waste of`(4-2) + (4-3) + (8-5) = 6`

.

Return *the minimum total wasted space by choosing the box supplier optimally, or *. Since the answer may be

`-1`

if it is impossible to fit all the packages inside boxes**large**, return it

**modulo**

`10^9 + 7`

.**Example 1:**

**Input:** packages = [2,3,5], boxes = [[4,8],[2,8]]

**Output:** 6

**Explanation:** 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.

**Example 2:**

**Input:** packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]

**Output:** -1

**Explanation:** There is no box that the package of size 5 can fit in.

**Example 3:**

**Input:** packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]

**Output:** 9

**Explanation:** 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.

**Constraints:**

`n == packages.length`

`m == boxes.length`

`1 <= n <= 10^5`

`1 <= m <= 10^5`

`1 <= packages[i] <= 10^5`

`1 <= boxes[j].length <= 10^5`

`1 <= boxes[j][k] <= 10^5`

`sum(boxes[j].length) <= 10^5`

- The elements in
`boxes[j]`

are**distinct**.

## Solution

Obviously, each package should be placed in the box such that the size of the box is at least the size of the package and the size of the box should be as small as possible.

Sort `packages`

and each row of `boxes`

. Then calculate the prefix sums of `packages`

. For each row of `boxes`

, if the size of the largest box is still less than the size of the largest box, then the row is not available, so continue. Otherwise, for each box, use binary search to find the maximum package size that can be placed in the box, and calculate the wasted space. When all boxes in a row of `boxes`

are looped over, the total wasted space can be calculated.

After all rows of `boxes`

are looped over, the minimum wasted space can be calculated.

```
class Solution {
public int minWastedSpace(int[] packages, int[][] boxes) {
final int MODULO = 1000000007;
int n = packages.length, m = boxes.length;
Arrays.sort(packages);
for (int i = 0; i < m; i++)
Arrays.sort(boxes[i]);
long[] packagesPrefixSum = new long[n];
packagesPrefixSum[0] = packages[0];
for (int i = 1; i < n; i++)
packagesPrefixSum[i] = packagesPrefixSum[i - 1] + packages[i];
long minWasted = Long.MAX_VALUE;
int maxPackage = packages[n - 1], minPackage = packages[0];
for (int[] curBoxes : boxes) {
int count = curBoxes.length;
if (curBoxes[count - 1] < maxPackage)
continue;
int last = -1;
long totalWasted = 0;
for (int i = 0; i < count; i++) {
int box = curBoxes[i];
if (box < minPackage)
continue;
int index = lastIndex(packages, box);
long totalSpace = packagesPrefixSum[index] - (last < 0 ? 0 : packagesPrefixSum[last]);
long wastedSpace = (long) (index - last) * box - totalSpace;
totalWasted += wastedSpace;
last = index;
}
minWasted = Math.min(minWasted, totalWasted);
}
return minWasted == Long.MAX_VALUE ? -1 : (int) (minWasted % MODULO);
}
public int lastIndex(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
if (arr[mid] <= target)
low = mid;
else
high = mid - 1;
}
return low;
}
}
```