Question

1889. Minimum Space Wasted From Packaging

中文文档

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 ith package. The suppliers are given as a 2D integer array boxes, where boxes[j] is an array of box sizes that the jth 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 _-1 if it is impossible to fit all the packages inside boxes. Since the answer may be large, return it modulo 109 + 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 <= 105
• 1 <= m <= 105
• 1 <= packages[i] <= 105
• 1 <= boxes[j].length <= 105
• 1 <= boxes[j][k] <= 105
• sum(boxes[j].length) <= 105
• The elements in boxes[j] are distinct.

Solutions

Solution 1

class Solution:
  def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
    mod = 10**9 + 7
    ans = inf
    packages.sort()
    for box in boxes:
      box.sort()
      if packages[-1] > box[-1]:
        continue
      s = i = 0
      for b in box:
        j = bisect_right(packages, b, lo=i)
        s += (j - i) * b
        i = j
      ans = min(ans, s)
    if ans == inf:
      return -1
    return (ans - sum(packages)) % mod

class Solution {
  public int minWastedSpace(int[] packages, int[][] boxes) {
    int n = packages.length;
    final long inf = 1L << 62;
    Arrays.sort(packages);
    long ans = inf;
    for (var box : boxes) {
      Arrays.sort(box);
      if (packages[n - 1] > box[box.length - 1]) {
        continue;
      }
      long s = 0;
      int i = 0;
      for (int b : box) {
        int j = search(packages, b, i);
        s += 1L * (j - i) * b;
        i = j;
      }
      ans = Math.min(ans, s);
    }
    if (ans == inf) {
      return -1;
    }
    long s = 0;
    for (int p : packages) {
      s += p;
    }
    final int mod = (int) 1e9 + 7;
    return (int) ((ans - s) % mod);
  }

  private int search(int[] nums, int x, int l) {
    int r = nums.length;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] > x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

class Solution {
public:
  int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
    int n = packages.size(), m = boxes.size();
    sort(packages.begin(), packages.end());
    const int mod = 1e9 + 7;
    const long long inf = 1LL << 62;
    long long ans = inf;
    for (auto& box : boxes) {
      sort(box.begin(), box.end());
      if (packages.back() > box.back()) {
        continue;
      }
      int i = 0;
      long long s = 0;
      for (auto& b : box) {
        int j = upper_bound(packages.begin() + i, packages.end(), b) - packages.begin();
        s += 1LL * (j - i) * b;
        i = j;
      }
      ans = min(ans, s);
    }
    return ans == inf ? -1 : (ans - accumulate(packages.begin(), packages.end(), 0LL)) % mod;
  }
};

func minWastedSpace(packages []int, boxes [][]int) int {
  n := len(packages)
  inf := 1 << 62
  sort.Ints(packages)
  ans := inf
  for _, box := range boxes {
    sort.Ints(box)
    if packages[n-1] > box[len(box)-1] {
      continue
    }
    s, i := 0, 0
    for _, b := range box {
      j := sort.SearchInts(packages[i:], b+1) + i
      s += (j - i) * b
      i = j
    }
    ans = min(ans, s)
  }
  if ans == inf {
    return -1
  }
  s := 0
  for _, p := range packages {
    s += p
  }
  const mod = 1e9 + 7
  return (ans - s) % mod
}

function minWastedSpace(packages: number[], boxes: number[][]): number {
  const n = packages.length;
  const inf = Infinity;
  packages.sort((a, b) => a - b);
  let ans = inf;
  for (const box of boxes) {
    box.sort((a, b) => a - b);
    if (packages[n - 1] > box[box.length - 1]) {
      continue;
    }
    let s = 0;
    let i = 0;
    for (const b of box) {
      const j = search(packages, b, i);
      s += (j - i) * b;
      i = j;
    }
    ans = Math.min(ans, s);
  }
  if (ans === inf) {
    return -1;
  }
  const s = packages.reduce((a, b) => a + b, 0);
  return (ans - s) % 1000000007;
}

function search(nums: number[], x: number, l: number): number {
  let r = nums.length;
  while (l < r) {
    const mid = (l + r) >> 1;
    if (nums[mid] > x) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return l;
}