**You have to paint N boards of length {A**_{0}, A_{1}, A_{2} … A_{N-1}}. There are *K* painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

**Hint:**

**Try to think how to apply Binary Search indirectly to solve this problem. First, it does not require A to be sorted in any way. Second, if you sort A, the constraint that the painter must paint continuous sections of board does not necessarily hold anymore. Think carefully: What if you have a maximum board length in mind such that no painter can exceed this value?**

Sponsored: https://www.wanderful.io has published a chatbot, who can chat with you and help you find apartments in San Francisco and Bay area. Check it out: http://m.me/wanderful.io

C++:

01 int min_time(int A[],int size,int k)

02 {

03 int sum=0;

04 for(int i=0;i<size;i++)

05 sum+=A[i];

06 int lo=1;

07 int hi=sum;

08 while(lo<hi){

09 int t=1;

10 int mid=(lo+hi)/2;

11 sum=0;

12 for(int i=0;i<size;i++){

13 sum+=A[i];

14 if(sum>mid){

15 i—;

16 t++;

17 sum=0;

18 }

19 }

20 if(t>k)

21 lo=mid+1;

22 else if(t<=k)

23 hi=mid;

24 }

25 return hi;

26 }

### Like this:

Like Loading...

*Related*