Minimum Space Wasted From Packaging LeetCode solution in C++

1
class Solution {
2
 public:
3
#define MOD 1000000007
4
#define ll long long
5
  int minWastedSpace(vector<int> &packages, vector<vector<int>> &boxes) {
6
    int n = packages.size();
7
    int m = boxes.size();
8
    sort(packages.begin(), packages.end());
9
    vector<ll> pack(n + 1);
10
    pack[0] = 0;
11
    for (int i = 0; i < n; i++) {
12
      pack[i + 1] = packages[i];
13
      pack[i + 1] += pack[i];
14
    }
15
    ll ans = 1e18;
16
    bool mf = false;
17
    for (int i = 0; i < m; i++) {
18
      vector<int> opt = boxes[i];
19
      sort(opt.begin(), opt.end());
20
      int back = 0;
21
      ll temp = 0;
22
      bool flag = false;
23
      ll bag;
24
      for (int j = 0; j < (int)opt.size(); j++) {
25
        bag = opt[j];
26
        auto it = upper_bound(packages.begin(), packages.end(), bag);
27
        auto it1 = it;
28
        int idx;
29
        if (it != packages.begin()) {
30
          it--;
31
          idx = it - packages.begin();
32
          ll num_packs = idx + 1 - back;
33

34
          ll pack_sum = pack[idx + 1] - pack[back];
35
          back = idx + 1;
36
          temp += (num_packs * bag - pack_sum);
37
        }
38
        if (it1 == packages.end()) {
39
          flag = true;
40
          break;
41
        }
42
      }
43
      if (flag) {
44
        ans = min(ans, temp);
45
        mf = true;
46
      }
47
    }
48
    if (!mf) return -1;
49

50
    if (ans == 1e18) return -1;
51
    ans = ans % MOD;
52
    return ans;
53
  }
54
};