Skip to content

1889. Minimum Space Wasted From Packaging 👍

  • Time: $O(\texttt{sort}(n) + \texttt{sort}(m) + m\log n)$, where $n = |\texttt{packages}|$ and $m = |\texttt{boxes}|$
  • Space: $O(\texttt{sort}(n) + \texttt{sort}(m))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
    constexpr int kMod = 1'000'000'007;
    constexpr long kInf = 1e11;
    const long packagesSum = accumulate(packages.begin(), packages.end(), 0L);
    long minBoxesSum = kInf;

    ranges::sort(packages);

    for (vector<int>& box : boxes) {
      ranges::sort(box);
      if (box.back() < packages.back())
        continue;
      long accu = 0;
      long i = 0;
      for (const int b : box) {
        const long j = firstGreaterEqual(packages, b + 1);
        accu += b * (j - i);
        i = j;
      }
      minBoxesSum = min(minBoxesSum, accu);
    }

    return minBoxesSum == kInf ? -1 : (minBoxesSum - packagesSum) % kMod;
  }

 private:
  int firstGreaterEqual(const vector<int>& A, int target) {
    return ranges::lower_bound(A, target) - A.begin();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
  public int minWastedSpace(int[] packages, int[][] boxes) {
    final int kMod = 1_000_000_007;
    final long kInf = (long) 1e11;
    final long packagesSum = Arrays.stream(packages).mapToLong(p -> p).sum();
    long minBoxesSum = kInf;

    Arrays.sort(packages);

    for (int[] box : boxes) {
      Arrays.sort(box);
      if (box[box.length - 1] < packages[packages.length - 1])
        continue;
      long accu = 0;
      long i = 0;
      for (final int b : box) {
        final long j = firstGreaterEqual(packages, b + 1);
        accu += b * (j - i);
        i = j;
      }
      minBoxesSum = Math.min(minBoxesSum, accu);
    }

    return minBoxesSum == kInf ? -1 : (int) ((minBoxesSum - packagesSum) % kMod);
  }

  private int firstGreaterEqual(int[] A, int target) {
    int l = 0;
    int r = A.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (A[m] >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
    ans = math.inf

    packages.sort()

    for box in boxes:
      box.sort()
      if box[-1] < packages[-1]:
        continue
      accu = 0
      i = 0
      for b in box:
        j = bisect.bisect(packages, b, i)
        accu += b * (j - i)
        i = j
      ans = min(ans, accu)

    return -1 if ans == math.inf else (ans - sum(packages)) % int(1e9 + 7)