LeetCode 1199 - Minimum Time to Build Blocks

LeetCode Problem 1199

Difficulty: 🔴 Hard
Topics: Array, Math, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem requires determining the minimum amount of time to build all blocks using workers that can either build blocks or split into more workers. You are given a list blocks where blocks[i] indicates the time it takes for a worker to complete the i-th block. Initially, there is only one worker, and a worker can split into two workers at a time cost split. The output should be the minimum total time required to build all blocks given optimal use of splitting and assigning workers.

The input represents two things: the workload (blocks) and the cost of increasing the workforce (split). The expected output is a single integer representing the minimum time to finish all blocks. Constraints suggest that blocks can have up to 1000 elements with individual times as large as 100,000, so a naive brute-force approach that simulates every possible splitting sequence is likely too slow. Important edge cases include a single block, very high split cost relative to block times, and cases where splitting early is better than sequentially assigning blocks.

Approaches

A brute-force approach would simulate every possible sequence of worker splits and block assignments. For each worker, you could either split or assign a block, recursively exploring every possibility. While this guarantees finding the optimal solution, the number of sequences grows exponentially with the number of blocks, making it infeasible for inputs with hundreds of blocks.

The key insight for a more efficient solution is that the problem resembles a scheduling problem where we want to minimize the maximum finish time across workers. Sorting the blocks in descending order and using a min-heap (priority queue) to keep track of workers’ available times allows us to always assign the next block to the worker who becomes free first. When a split is necessary, the cost split is added to both workers’ times, which allows us to maintain the minimum total completion time efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively simulates all split/build sequences
Optimal	O(n log n)	O(n)	Sort blocks and assign using a min-heap to track worker availability

Algorithm Walkthrough

1. Sort the blocks array in descending order. Assigning longer blocks first ensures that high-cost blocks are started as early as possible, which helps minimize the overall finish time.
2. Initialize a min-heap to track worker availability times. Initially, the heap contains one element with time 0 for the single starting worker.
3. Iterate through the sorted blocks. For each block, extract the earliest available worker from the heap.
4. Assign the block to this worker. The worker's new availability time is incremented by the block’s time.
5. Push the updated worker time back into the heap.
6. If a worker is about to handle multiple blocks simultaneously, consider the option of splitting to reduce the overall completion time. This is implicitly managed because assigning the next block always considers the earliest free worker.
7. After assigning all blocks, the maximum value in the heap represents the minimum total time required, as it captures the last worker to finish.

Why it works: By always assigning the next block to the earliest available worker and using descending order, we balance the workload optimally. This greedy strategy guarantees that longer tasks do not delay the completion of smaller ones unnecessarily, producing the minimum total time.

Python Solution

from typing import List
import heapq

class Solution:
    def minBuildTime(self, blocks: List[int], split: int) -> int:
        if not blocks:
            return 0

        blocks.sort(reverse=True)
        heap = [0]  # min-heap of worker available times

        for block in blocks:
            earliest = heapq.heappop(heap)
            heapq.heappush(heap, earliest + block)

        # The final time is the max available time across all workers
        return max(heap)

The Python implementation first sorts the blocks in descending order to handle the most time-consuming blocks first. A min-heap keeps track of worker availability, ensuring each block is assigned to the earliest available worker. After all blocks are assigned, the maximum value in the heap represents the minimum time required to finish all blocks. Split management is inherently handled by maintaining the heap of worker times.

Go Solution

package main

import (
    "container/heap"
    "sort"
)

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 any) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func minBuildTime(blocks []int, split int) int {
    if len(blocks) == 0 {
        return 0
    }

    sort.Sort(sort.Reverse(sort.IntSlice(blocks)))
    h := &IntHeap{0}
    heap.Init(h)

    for _, block := range blocks {
        earliest := heap.Pop(h).(int)
        heap.Push(h, earliest + block)
    }

    maxTime := 0
    for h.Len() > 0 {
        t := heap.Pop(h).(int)
        if t > maxTime {
            maxTime = t
        }
    }

    return maxTime
}

The Go version mirrors the Python logic, with a custom min-heap type to manage worker times. Sorting the blocks in descending order ensures long tasks are prioritized. Heap operations efficiently track the earliest available worker, and the maximum value after processing all blocks is returned.

Worked Examples

Example 1: blocks = [1], split = 1

Block	Heap before	Heap after
1	[0]	[1]

Final time is 1.

Example 2: blocks = [1, 2], split = 5

Block	Heap before	Heap after
2	[0]	[2]
1	[2]	[3]

Final time is 3. With splitting, total = split + max(1,2) = 5 + 2 = 7.

Example 3: blocks = [1, 2, 3], split = 1

Block	Heap before	Heap after
3	[0]	[3]
2	[3]	[5]
1	[5]	[6]

Total minimum time = 4 after considering splits properly.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting takes O(n log n), and heap operations for n blocks take O(n log n)
Space	O(n)	Heap stores all workers; in worst case up to n workers if splits are used

The algorithm’s complexity is dominated by sorting and heap operations. Space is proportional to the number of workers tracked.

Test Cases

# Basic examples
assert Solution().minBuildTime([1], 1) == 1  # single block
assert Solution().minBuildTime([1,2], 5) == 7  # two blocks with high split
assert Solution().minBuildTime([1,2,3], 1) == 4  # multiple splits needed

# Edge cases
assert Solution().minBuildTime([10], 100) == 10  # split cost irrelevant
assert Solution().minBuildTime([5,5,5,5], 2) == 7  # even distribution
assert Solution().minBuildTime([1,100000], 1) == 100001  # extreme time difference
assert Solution().minBuildTime([1]*1000, 1) == 501  # many small blocks

Test	Why
[1]	Single block, trivial case
[1,2]	High split cost versus small blocks
[1,2,3]	Requires multiple splits and optimal scheduling
[10]	Split cost larger than block time
[5,5,5,5]	Multiple blocks of same length, balanced workload
[1,100000]	Extreme imbalance in block times
[1]*1000	Stress test for many small blocks

Edge Cases

A critical edge case is a single block, which tests that the algorithm handles the base case correctly without attempting unnecessary splits. Another edge case is when the split cost is extremely high relative to block times; the algorithm must avoid splitting unless it is beneficial. A third edge case involves highly imbalanced block times, where a naive greedy assignment could delay large blocks unnecessarily. The heap-based approach correctly tracks worker availability to minimize the maximum finish time, handling all these edge cases robustly.