How to approach this problem

#1

please tell the logic to solve this problem

#2

Hello @pragyachoudhary1111,

K: number of painters
conditions:

  1. Each painter takes 1 unit of time to paint 1 unit of the board.
  2. A board can only be painted by 1 painter at maximum. This indicates that 2 or more painters cannot paint the same board
    N: number of boards to be painted

INPUTS:
3
5
1 2 3 4 5

OUTPUT:
5

Explanation :
Initially, there three painters available.
so, the first is assigned the board with a maximum unit of size i.e. 5 in this case (it will take 5 units of time)
the second painter is assigned to paint the second max. sized board i.e. 4 unit sized board (4 unit of time)
the third, which is the last painter is given 3 unit sized board to paint. (he will take 3 units of time)

After 3 unit of time:
the third painter is free.
so, now he is assigned the 2 unit sized board to paint. (it will 2 unit of time)
so, the total unit of time for which the third painter was busy painting(till now)=3+2=5;

After 4 unit of time:
the second painter is free.
so, now he is assigned the 1 unit sized board to paint. (it will 1 unit of time)
so, the total unit of time for which the second painter was busy painting(till now)=4+1=5;

After 5 unit of time:
All three painters are free. But, there is no board left to paint.
so, minimum time required to paint all boards are 5 unit

I hope this would help you better understand the problem.

APPROACH:
We know that the invariant of binary search has two main parts:

  1. the target value would always be in the searching range.
  2. the searching range will decrease in each loop so that the termination can be reached.

We also know that the values in this range must be in sorted order. Here our target value is the maximum sum of a contiguous section in the optimal allocation of boards. Now how can we apply the binary search for this? We can fix the possible low to high range for the target value and narrow down our search to get the optimal allocation.

We can see that the highest possible value in this range is the sum of all the elements in the array and this happens when we allot 1 painter all the sections of the board. The lowest possible value of this range is the maximum value of the array max, as in this allocation, we can allot max to one painter and divide the other sections such that the cost of them is less than or equal to the max and as close as possible to the max. Now if we consider we use x painters in the above scenarios, it is obvious that as the value in the range increases, the value of x decreases and vice-versa. From this, we can find the target value when x=k and use a helper function to find x, the minimum number of painters required when the maximum length of section a painter can paint is given.

Hope, this would help.

1 Like