Minimum time to build blocks

Array Math Greedy Heap (Priority Queue)

46.5% acceptance

Mar 31, 2026

240

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_build_time(mut blocks: Vec<i32>, split: i32) -> i32 {
    // Huffman-like approach: use a min-heap, merge two smallest repeatedly
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let mut heap: BinaryHeap<Reverse<i32>> = blocks.into_iter().map(Reverse).collect();
    while heap.len() > 1 {
      let a = heap.pop().unwrap().0;
      let b = heap.pop().unwrap().0;
      // The worker splits (costs `split` time), then the two workers handle a and b in parallel
      heap.push(Reverse(b.max(a) + split));
    }
    heap.pop().unwrap().0
  }
}