Leetcode 1199: Minimum Time to Build Blocks

https://leetcode.com/contest/biweekly-contest-9/problems/minimum-time-to-build-blocks/

Notes:

My thinking to this question is using memorization (or dp if you like). There are two keys parameters: one is the un-build blocks and the other one is number of worker.

At each stage, we have two directions to go:

One is that we have w workers, then we can try assign 1 to w workers to the blocks sorted form the largest to the smallest; and we need to figure out which way is the fastest;

The other is that we can do the splitting first. The maximum times of splitting is that when the number of workers is the same as that of the un-build blocks.

But this method received TLE.  Anyway, see the code below:

class Solution {
public:
    int minBuildTime(vector<int>& blocks, int split) {
        int len = blocks.size();
        vector<vector<int>> memo(len+1, vector<int>(2*len+1, -1));
        sort(blocks.begin(), blocks.end());
        return dfs(blocks, len, 1, split, memo);
    }

private:
    int dfs(vector<int> &bs, int len, int w, int &spt, vector<vector<int>> &memo) {
        if(len<1) return 0;
        if(len <= w) return bs[len-1];
        if(memo[len][w] != -1) return memo[len][w];
        int t = INT_MAX;
        for(int i=1; i<w; ++i) {
            if(bs[len-1] >= t) break;
            t = min(t, max(bs[len-1], dfs(bs, len-i, w-i, spt, memo)));
        }
        for(int i=1; (1<<i)*w<=len*2; ++i) {
            if(spt*i >= t) break;
            t = min(t, spt*i + dfs(bs, len, w*(1<<i), spt, memo));
        }
        return memo[len][w] = t;
    }
};

After searching online, it is found that this question can be solved by using Huffman Tree algorithm. Just opposite to starting with the largest block, we can start with the smallest one.

Each step, we just need to finish the current smallest one, then updated the second smallest one by adding split time. Then continue the iteration process, until only one element remaining, which is the shortest time.

Unbelievable? right. What is the key logic? To be continued...

See the code below:

class Solution {
public:
    int minBuildTime(vector<int>& blocks, int split) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (auto &b : blocks) pq.push(b);
        while(pq.size() > 1) {
            pq.pop();
            int t = pq.top();
            pq.pop();
            pq.push(t + split);
        }
        return pq.top();
    }
};