We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Build Blocks

Number: 1167

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given an array “blocks” where blocks[i] is the time required to build the i‑th block, and an integer “split” representing the cost for any worker to split into two workers, determine the minimum total time required to build all blocks. Initially there is one worker; a worker may either build one block (and then go home) or split (which produces two workers, at a cost of “split” time for that worker). Notice that if several workers split concurrently the cost is incurred only once in that time unit. The goal is to schedule splits and assignments so that each block is built exactly by one worker and the overall time (which is the maximum time taken on any branch) is minimized.

Key Insights

  • To build more than one block, splitting is necessary; however, each split “ages” the worker (increases its “depth”) so that the subsequent block built by that worker will finish later.
  • The time needed on a branch equals (number of splits on that branch)×split + block’s building time.
  • If we decide on a total allowed time T, then a block with build time b must be built along a branch that had at most floor((T – b)/split) splits.
  • An optimal strategy is equivalent to “assigning” each block to a leaf in a binary splitting tree – the leaf’s “depth” is the number of splits used before building.
  • One may show that if we want to produce n leaves (n blocks) in an optimally “balanced” way then the best achievable multiset of depths is the one obtained by “greedily splitting” the available worker with the smallest depth until n leaves are available.
  • Then, by sorting the blocks in descending order and pairing the largest block with the leaf that has the smallest depth (i.e. the “most efficient” branch), one sees that a candidate time T is feasible if for every block (after appropriate ordering) the allowed splits for that block (floor((T – block)/split)) is at least the corresponding optimal leaf depth.

Space and Time Complexity

Time Complexity: O(n log n + n log nTree) per feasibility check (n up to 1000) and multiplied by binary search iterations. Overall it is O(n (log n + log(MaxTime))). Space Complexity: O(n) for sorting and storing the optimal depths.

Solution

We solve the problem using binary search on the total allowed time T. For a candidate T, we need to decide if we can “assign” every block to a worker branch such that for a block with build time b, the branch used had at most allowed splits L = floor((T – b)/split). (If T < b then T is not feasible.) To “simulate” the worker‐splitting process optimally, we generate the multiset of the minimum branch‐depths possible for n blocks. This is done by starting with one worker (depth 0) and repeatedly “splitting” (removing a worker with the smallest depth and replacing it with two workers of depth+1) until we have exactly n leaves. We then sort these optimal depths in non‐decreasing order. Also, for each block we compute its allowed maximum number of splits as floor((T – block)/split); sorting these allowed values in non‑decreasing order (so that the block with the largest build time is paired with the smallest depth) allows us to “match” the leaves with the blocks. If every optimal leaf depth is less than or equal to the allowed splits for its corresponding block, then T is feasible.

The binary search runs over T in the range [min(blocks), max(blocks) + split * n] to be safe. The final answer is the minimum T for which a feasible assignment exists.

We now show code solutions in Python, JavaScript, C++ and Java with detailed comments.

Code Solutions

# Python solution for "Minimum Time to Build Blocks"

import heapq
import math

def min_time_to_build_blocks(blocks, split):
    n = len(blocks)
    
    # Function to compute the optimal multiset of branch depths for n leaves
    # using greedy splitting. We use a min-heap to always split the smallest depth available.
    def get_optimal_depths(n):
        heap = [0]  # starting with one worker having depth 0
        # The current number of leaves available.
        leaves = 1  
        while leaves < n:
            # Pop the worker with the smallest depth
            depth = heapq.heappop(heap)
            # When a worker splits, it is replaced by two new workers with depth+1.
            heapq.heappush(heap, depth + 1)
            heapq.heappush(heap, depth + 1)
            leaves += 1  # each split increases the total leaf count by 1
        # Return the sorted list of depths for assignment.
        return sorted(heap)
    
    optimal_depths = get_optimal_depths(n)
    
    # Check function to test if candidate total time T is sufficient
    def can_build_all(T):
        allowed = []
        for b in blocks:
            if T < b:
                return False  # not enough time to build this block even without any split
            allowed_splits = (T - b) // split
            allowed.append(allowed_splits)
        allowed.sort()  # sort allowed splits in non-decreasing order
        for i in range(n):
            # For each block, the branch chosen must have a depth no more than allowed splits.
            if optimal_depths[i] > allowed[i]:
                return False
        return True

    # Set binary search boundaries.
    lo = min(blocks)
    hi = max(blocks) + split * n  # an upper bound; n splits in worst-case
    
    res = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_build_all(mid):
            res = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return res

# Example usage:
if __name__ == "__main__":
    # Example 1:
    blocks = [1]
    split_cost = 1
    print(min_time_to_build_blocks(blocks, split_cost))  # Expected output: 1

    # Example 2:
    blocks = [1,2]
    split_cost = 5
    print(min_time_to_build_blocks(blocks, split_cost))  # Expected output: 7

    # Example 3:
    blocks = [1,2,3]
    split_cost = 1
    print(min_time_to_build_blocks(blocks, split_cost))  # Expected output: 4
← Back to All Questions