Regarding painter's problem

#1

https://ide.codingblocks.com/s/71001.In this code all test cases are not being passed.

#2

Hi Raushan, in this problem you have to apply binary search BUT not on the array. You have to apply binary search to find out the maximum no. of planks a painter can paint. Now what all values can it take. A painter can paint at maximum all the planks so we have the hi as sum of all array elements. And at minimum we can make one painter paint the plank which is longest, so we have lo as max of array. Now mid will give you the no. of units of plank. Check if you can assign your painters to paint mid no. of units of plank or not.
Consider the below example

// Input
n = 5
k = 3
arr = 2 5 3 6 1

Now hi = 17, lo = 6
mid = 10
so now what you do is:
give that no. of units of plank to a painter such that it dosent exceed 10.
Now you can give boards:
2, 5, 3 to 1 painter
6, 1 to the second.

Since you have 3 painters and you are able to make a distribution such that each painter gets 10 or less units to paint, 10 is one valid answer.

now since you need to find minimum time, keep 10 as the potential ans. and find if there exists any other ans which is less than 10.

Hope you understand now that on what thing you have to apply binary search. :slight_smile:

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.