Last Updated: 14 Apr, 2021
Minimum Time To Build Blocks
Easy
Asked in companies
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.
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
Approaches
- 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’.