Problem statement

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

Solution 1

Let dp(i, w) be minimum time we can get if we did all jobs before x and at current moment we have w workers. Then we have several options in given moment of time:

  1. Allow one worker do the B[i], notice that it is always better to choose the block with bigger time for worker who take it earlier, so we sorted B in reverse order in the beginning.
  2. Split all workers, so now we have 2*w of them.

Why this is enough? Imagine the case when we have jobs a1, a2, a3, a4, a5, a6, a7, a8, a9, a10 and w = 7 workers. On each step we need to use all workers: so no one of them is vacant. For example it can happen that we can have 3 workers doing jobs [a1, a2, a3] and other 4 workers split. We spend for this max(a1, split) time and now we have a4, a5, a6, a7, a8, a9, a10 jobs and w = 8 workers. Note that in fact it is equivalent to steps 1, 1, 1, 2, because we have decreasing property of our B.

Complexity

Time complexity is O(n^2), space also O(n^2), unfortunately it will give TLE, I do not know why it happens though, n is not big enough.

Code

class Solution:
    def minBuildTime(self, B, split):
        B = sorted(B)[::-1]
        n = len(B)

        @lru_cache(None)
        def dp(i, w):
            if i == n: return 0
            if w == 0: return float("inf")
            ans = float("inf")
            if w < n: ans = split + dp(i, min(n, 2*w))
            ans = min(ans, max(B[i], dp(i+1, w-1)))
            return ans

        return dp(0, 1)

Solution 2

In fact there is better solution, using the idea of Huffman Tree. We can represent our problem as tree, where we when we split we draw two children for node. Or we can do the job and it means that we reached the leaf. So, minimization problem is now the following:

\(\min\limits_{trees} \left[ \max\limits_x \left( f(x) + s\cdot d(x) \right) \right],\) where $f(x) = B[x]$ and $d(x)$ are depths of leaf in our tree. It is not the same as classical Huffmat Tree, where we have

\[\min\limits_{trees} \sum\limits_x f(x) \cdot d(x)\]

I do not have a proof why the greedy strategy works here: the idea is to take two smallest elements and merge them, so we have node with two subtrees and weight now is max(x, y) + split and continue this process in greedy way.

Complexity

Time complexity is O(n*log n), space is O(n).

Code

class Solution:
    def minBuildTime(self, blocks, split):
        heapify(blocks)
        while len(blocks) > 1:
            x, y = heappop(blocks), heappop(blocks)
            heappush(blocks, y + split)
        return blocks[0]