Boards of given lengths must be painted by k painters, each painting a contiguous group. Painters work at the same time, so minimize the time taken by the busiest painter.
DSA Animator › DSA Revision › Binary Search › The Painter's Partition Problem
Remember: books, painters and ships are the same pattern. Binary search the busiest load, and check it greedily. The video solves The Painter's Partition Problem (InterviewBit, Hard) with the Binary Search on Answer pattern from the Binary Search topic, and you can replay every step in the interactive The Painter's Partition Problem animation.
Boards of given lengths must be painted by k painters, each painting a contiguous group. Painters work at the same time, so minimize the time taken by the busiest painter.
For boards 10, 20, 30, 40 and 2 painters, the answer is 60. One paints 10, 20, 30, and the other paints 40.
Trying every partition is exponential. Again, if a time limit works, any bigger limit also works.
Binary search the time limit between the longest board and the total. Assign boards greedily, starting a new painter when the limit would be exceeded. If at most k painters are needed, try smaller.
The range is 40 to 100. 70 works, but 55 needs 3 painters. 63 works, and 59 does not. 61 works, and so does 60. So the answer is 60.
In code, low is the longest board and high is the total length. The check counts painters greedily. Move high to mid when it works, otherwise move low past mid. It's O of n log of the total length, multiplied by the time per unit if the problem gives one.
Remember: books, painters and ships are the same pattern. Binary search the busiest load, and check it greedily.