leetcode/algorithms/cpp/minimumSpaceWastedFromPackaging/minimumSpaceWastedFromPackaging.cpp at main · MichelleZ/leetcode · GitHub

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
// Source: https://leetcode.com/problems/minimum-space-wasted-from-packaging/
// Author: Miao Zhang
// Date:   2021-06-17

class Solution {
public:
    int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
        int kMod = 1e9 + 7;
        int n = packages.size();
        sort(begin(packages), end(packages));
        vector<long long> sums(n + 1);
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + packages[i - 1];
        }
        auto get = [&] (int left, int right) {
            return sums[right + 1] - sums[left];
        };
        long long res = LLONG_MAX;
        for (auto& box: boxes) {
            sort(begin(box), end(box));
            if (packages.back() > box.back()) continue;
            auto pt = packages.begin();
            long long total = 0;
            for (int b: box) {
                if (b < *pt) continue;
                auto ptnxt = prev(upper_bound(pt, packages.end(), b));
                total += (long long)(ptnxt - pt + 1) * b - get(pt - packages.begin(), ptnxt - packages.begin());
                pt = next(ptnxt);
                if (pt == packages.end()) break;
            }
            res = min(res, total);
        }
        return (res == LLONG_MAX ? -1 : res % kMod);
    }
};