Painter Partition Problem (Binary Search)

Hello!

This post is about solution of Codebuddy problem Painter Partition :  visit question here

So, we will be looking at the implementation part of it using Binary Search.

We encourage you to try solving problem first by yourself but still if you are getting trouble then move on to tutorials.

Here we require to minimise the time taken to paint all boards given the number of painters and time taken by each painter to paint a board:

Please note that time taken will be minimised when board length per person is minimised. So, we will manipulate our problem and we will minimise the board length per person that will in turn minimise time taken.

Constraints:
1.  Two painters cannot share a board to paint.
2.  A painter will paint only contiguous section of boards.





 Now for Example:

Sample Input:

1
2 2 5
1 10

In this case:

There are two boards of length 1 and 10 each and time taken by each painter is to paint a unit length of board is: 5. Hence the minimum time is taken when we assign both painter to two boards. Hence 1st painter will take 1*5= 5 unit of time and second person will take 10*5 = 50 unit amount of time.
Hence total time taken to complete this task is 50 units of time.



Approach:

1. Here we will apply binary search on "length of board allocated" to each painter.
2. Note that maximum length of board from all available boards will be the least length per painter because since a board cannot be shared by two painters, hence there will be at least one painter who will paint that board, so minimum length of board per painter is max of length of boards.
3. The maximum length a painter can paint is sum of all board length present. That is one painter only paints all the boards.
4. Hence after applying binary search to (max length, sum of lengths) we will check if that length per painter satisfies the constraints and all painters can be allocated to the boards. Because length per painter will be minimum when all painters have been used.

Some code snippets are:

Binary search Code:

Check function code:

Important points:

1. long long int has been typedef to ll.

2. Checks function check the number of painters that can be allocated to all boards and if painters are more than given then length per person should be increased else length per person should be decreased.

3. Finally we can find the time taken by knowing the length per painter and painter who takes maximum time.

I have tried my best to explain solution in best possible manner. Try it and if you are facing any problem you can contact for solution or comment below.