Minimum Time to Build Blocks

hard heap greedy huffman

Problem

You are given a list blocks where blocks[i] is the time needed to build block i, and an integer split. You start with one worker. In one step a worker can either build one block (taking that block's time) or split into two workers (taking split time). A worker can only build one block and then is gone. Workers act in parallel, so the cost of a set of parallel actions is the maximum among them. Return the minimum time to build all blocks.

Inputblocks = [1, 2, 3], split = 1

Output4

Split (cost 1) into two workers. One builds block of time 1. The other splits again (cost 1) then those two build blocks of time 2 and 3 in parallel: 1 + 1 + max(2, 3) = ... the greedy merge yields 4.

blocks (comma-separated)

split

import heapq

def min_build_time(blocks, split):
    heap = list(blocks)
    heapq.heapify(heap)
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        heapq.heappush(heap, b + split)
    return heap[0]

function minBuildTime(blocks, split) {
  // min-heap via sorted insert (small inputs)
  const heap = blocks.slice().sort((a, b) => a - b);
  while (heap.length > 1) {
    const a = heap.shift();
    const b = heap.shift();
    const merged = b + split;
    let lo = 0, hi = heap.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (heap[mid] < merged) lo = mid + 1; else hi = mid;
    }
    heap.splice(lo, 0, merged);
  }
  return heap[0];
}

import java.util.PriorityQueue;

class Solution {
    public int minBuildTime(int[] blocks, int split) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int b : blocks) heap.offer(b);
        while (heap.size() > 1) {
            int a = heap.poll();
            int b = heap.poll();
            heap.offer(b + split);
        }
        return heap.poll();
    }
}

#include <queue>
#include <vector>
using namespace std;

int minBuildTime(vector<int>& blocks, int split) {
    priority_queue<int, vector<int>, greater<int>> heap(blocks.begin(), blocks.end());
    while (heap.size() > 1) {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        heap.push(b + split);
    }
    return heap.top();
}

Explanation

Here is a neat trick: instead of thinking about splitting workers, think about it backwards as merging blocks. This is exactly how a Huffman tree is built, and a min-heap makes it easy.

The cost of a worker handling two blocks is one split plus the time of the bigger block (they build in parallel, so the slower one decides the cost). To keep the total small, we want the two cheapest blocks to be the ones that share a split deepest in the tree.

So we put all block times in a min-heap. Each round we pop the two smallest, a and b (where b is the larger of the two). We discard a and push back b + split, which represents one combined "task" that now stands for both blocks. We repeat until a single value is left, and that is the answer.

Example: blocks = [1, 2, 3], split = 1. Pop 1 and 2; push back 2 + 1 = 3. Heap is now [3, 3]. Pop 3 and 3; push back 3 + 1 = 4. One value left, so the answer is 4.

By always merging the smallest piles first, the cheap blocks get the most splits stacked on top of them while the expensive blocks stay near the top, which keeps the overall time as low as possible.

Time: O(n log n) Space: O(n)