Minimum Time to Build Blocks

Problem

You are given a list of blocks, where blocks[i] = t means that the i-th block needs t units of time to be built. A block can only be built by exactly one worker.

A worker can either split into two workers (number of workers increases by one) or build a block then go home. Both decisions cost some time.

The time cost of spliting one worker into two workers is given as an integer split. Note that if two workers split at the same time, they split in parallel so the cost would be split.

Output the minimum time needed to build all blocks.

Initially, there is only one worker.

Examples

Example 1:

1
2
3


Input: blocks = [1], split = 1
Output: 1
Explanation: We use 1 worker to build 1 block in 1 time unit.

Example 2:

1
2
3


Input: blocks = [1,2], split = 5
Output: 7
Explanation: We split the worker into 2 workers in 5 time units then assign each of them to a block so the cost is 5 + max(1, 2) = 7.

Example 3:

1
2
3
4
5


Input: blocks = [1,2,3], split = 1
Output: 4
Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.

Constraints:

1 <= blocks.length <= 1000
1 <= blocks[i] <= 10^5
1 <= split <= 100

Solution

Method 1 – Greedy with Min-Heap

Intuition

To minimize the total time, we want to split workers only when it helps parallelize block building. By always combining the two smallest build times (using a min-heap), we ensure that splits are used efficiently, and the largest blocks are built last, minimizing the overall time.

Approach

Use a min-heap to store block build times.
While more than one block remains:
- Pop the two smallest times.
- The time to build both in parallel is split + max(a, b).
- Push this combined time back into the heap.
When one block remains, return its time.
This simulates optimal worker splitting and assignment.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


#include <queue>
class Solution {
public:
    int minBuildTime(vector<int>& blocks, int split) {
        priority_queue<int, vector<int>, greater<int>> pq(blocks.begin(), blocks.end());
        while (pq.size() > 1) {
            int a = pq.top(); pq.pop();
            int b = pq.top(); pq.pop();
            pq.push(split + max(a, b));
        }
        return pq.top();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


import "container/heap"
type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{}   { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }

func minBuildTime(blocks []int, split int) int {
    h := &IntHeap{}
    heap.Init(h)
    for _, b := range blocks { heap.Push(h, b) }
    for h.Len() > 1 {
        a := heap.Pop(h).(int)
        b := heap.Pop(h).(int)
        heap.Push(h, split+max(a, b))
    }
    return (*h)[0]
}
func max(a, b int) int { if a > b { return a } else { return b } }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    fun minBuildTime(blocks: IntArray, split: Int): Int {
        val pq = PriorityQueue<Int>()
        blocks.forEach { pq.add(it) }
        while (pq.size > 1) {
            val a = pq.poll()
            val b = pq.poll()
            pq.add(split + maxOf(a, b))
        }
        return pq.peek()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


import heapq
class Solution:
    def minBuildTime(self, blocks: list[int], split: int) -> int:
        h = blocks[:]
        heapq.heapify(h)
        while len(h) > 1:
            a = heapq.heappop(h)
            b = heapq.heappop(h)
            heapq.heappush(h, split + max(a, b))
        return h[0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


use std::collections::BinaryHeap;
impl Solution {
    pub fn min_build_time(blocks: Vec<i32>, split: i32) -> i32 {
        let mut heap = std::collections::BinaryHeap::new();
        for b in blocks { heap.push(-b); }
        while heap.len() > 1 {
            let a = -heap.pop().unwrap();
            let b = -heap.pop().unwrap();
            heap.push(-(split + a.max(b)));
        }
        -heap.pop().unwrap()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    minBuildTime(blocks: number[], split: number): number {
        const h = [...blocks].sort((a, b) => a - b);
        while (h.length > 1) {
            const a = h.shift()!;
            const b = h.shift()!;
            h.push(split + Math.max(a, b));
            h.sort((a, b) => a - b);
        }
        return h[0];
    }
}

Complexity

⏰ Time complexity: O(n log n) — Each heap operation is log n, and we do n merges.
🧺 Space complexity: O(n) — For the heap storing block times.

Problem#

Examples#

Solution#

Method 1 – Greedy with Min-Heap#

Intuition#

Approach#

Code#

Complexity#