Think the problem reversely

This week’s (Jun 5, 2021) 4th problem, we can solve it by thinking the problem process reversely.

1889. Minimum Space Wasted From Packaging

A naive approach got TLE

A naive approach is putting the pacakage in a map and traverse each package to see the smallest fit box. And harvest the results.

The time complexity is O(n*m*log m) where n is the length of the packages and m is the maximum length of the box. Since n and m can as large as 10⁵, this solution will get TLE.

typedef long long LL;
const int mod = 1e9+7;
const long long INF = 1e10+6;
class Solution {
public:
    int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
        LL ret =INF;
        map<int, int> cnt;
        for (auto p: packages)cnt[p]++;
        for (auto &box: boxes){
            sort(box.begin(), box.end());
            if (box.back() < cnt.rbegin()->first)continue;
            LL thisret = 0;
            for (auto [k, v]: cnt) {
                auto it = lower_bound(box.begin(), box.end(), k);
                thisret += v*(*it - k);
            }
            ret = min(ret, (LL)thisret);
        }
        return ret == INF? -1: ret%mod;  
    }
};

runtime

32 / 41 test cases passed.
Status: Time Limit Exceeded

A better way

We can think the problem reversely:

Previous solution is:

for package in packages

for box in boxes

We can try

for box in boxes:

binary search the box’s corresponding location in packages.

The improved algorithm has the complexity of O(m log n) where m is the length of the whole box and n is the length of the packages.

typedef long long LL;
const int mod = 1e9+7;
const long long INF = 1e10+6;
class Solution {
public:
    int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
        LL ret = INF, thisret = 0;
        sort(packages.begin(), packages.end());
        LL sum = accumulate(packages.begin(), packages.end(), 0ll);
        for (auto &box: boxes) {
            sort(box.begin(), box.end());
            if (box.back() < packages.back()) continue;
            thisret = 0;
            int last = -1;
            for (auto &b: box) {
                // find the larger than the current box's package location, then the rest part's packages will be all less or equal to the box.
                int newidx = upper_bound(packages.begin(), packages.end(), b) - packages.begin();
                if (newidx - 1 > last){
                    thisret += (LL)b*(newidx -1 - last);
                    last = newidx - 1;
                }
            }
            ret = min(ret, thisret -  sum);
        }
        return ret == INF? -1: ret%mod;  
    }
};

runtime

Runtime: 292 ms, faster than 87.50% of C++ online submissions for Minimum Space Wasted From Packaging.
Memory Usage: 110.1 MB, less than 50.00% of C++ online submissions for Minimum Space Wasted From Packaging.