Minimum Time To Build Blocks

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
LinkedInMeeshoMicrosoft

Problem statement

You are managing a project that is about building the blocks. You need ‘workers’ to build the ‘blocks’, and a block can only be built by exactly one worker (means once a worker assigned to a particular block he needs to finish it). A worker can either split into two workers or build a block then go home. There is an extra time cost associated with both of the operations.

You are given an array ‘BLOCK’ where ‘BLOCK[i]’ denotes the time required to build the ith block. You are also given an integer, ‘SPLIT’, which denotes the time required to split the worker. The process starts with only one worker. Your task is to find the “minimum time” required to build all the blocks.

Note: 
Two or more workers may split simultaneously so that the cost would be ‘SPLIT’ at that time.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains two positive integers, ‘N’, and ‘SPLIT’, denote the total number of blocks and the time required to split a worker.

The second line of each test case contains ‘N’ positive integers, where ith integer represents the time required to build the ith block.
Output Format: 
For each test case, print the “minimum time” required to build all the blocks. 

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^4
1 <= ‘SPLIT’ <= 100
1 <= ‘BLOCK[i]’ <= 10^4

Time Limit: 1sec
Sample Input 1:
1
1 3
4
Sample Output 1:
4
Explanation For Sample Input 1:
We don’t need to perform any split. We can directly use one worker to build one block in 4 units of time.
Sample Input 2:
1
2 3
1 2
Sample Output 2:
5
Hint

Try to use the concept of Huffman coding.

Approaches (1)
Greedy Based Approach
  • The idea here is to use the concept of Huffman Coding.
  • In the Huffman coding, we always select the smallest two elements and keep adding the summation of these two until the size becomes 1. A similar strategy can be applied here.
  • So, we require a min-heap to maintain the non-decreasing order after every operation. First, push all the elements of the array ‘BLOCK’ into the priority queue named pq.
  • The operation which we are going to perform is that, in each iteration, we pop the top two elements from the priority queue and push the summation of split time and the maximum of these two popped elements into the pq.
  • Finally, when the size of the pq becomes ‘1’, return the top element.

 

Let us try to visualize this by using an example, ‘BLOCK’ = [1, 2, 4, 5] , ‘SPLIT’ = 4.

 

Step 1: Min-heap at this step = [1, 2, 4, 5].

 

  • Pop 2 elements, i.e., pop 1 and 2.
  • Heap becomes [4, 5].
  • Insert 4 + max(1, 2) = 6.
  • Heap becomes [4, 5, 6].

 

Step 2:  Min-heap at this step = [ 4, 5, 6].

 

  • Pop 2 elements, i.e., pop 4 and 5.
  • Heap becomes [6].
  • Insert 4 + max(4, 5) = 9.
  • Heap becomes [6, 9].

 

Step 3:  Min-heap at this step = [6, 9].

 

  • Pop 2 elements, i.e., pop 6 and 9.
  • Heap becomes empty.
  • Insert 4 + max(6, 9) = 13.
  • Heap becomes [13].

 

Step 4:  Min-heap at this step = [13], i,e., the size is ‘1’ so we return the top element.

 

So, the total cost to build all blocks would be ‘13’.

Time Complexity

O(N * logN), where ‘N’ is the number blocks.

 

We are using the priority queue that takes O(logN) time to perform operations like push and pop. We are performing these operations ‘N’ times. So, the time complexity will be O(N * logN).

Space Complexity

O(N), where ‘N’ is the number blocks.

 

As we are using a priority queue that can have at max ‘N’ elements at a time. Hence, the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Minimum Time To Build Blocks
Full screen
Console