Given an array boards[] of board lengths and k painters, assign boards to painters such that: (1) each painter paints a contiguous segment of boards, (2) every board is painted by exactly one painter. Minimize the maximum time any single painter takes (time to paint a board equals its length).
boards = [10,20,30,40], k = 260boards = [10,10,10,10], k = 220boards = [5,10,30,20,15], k = 335lo = max(boards), hi = sum(boards)mid = lo + (hi−lo)/2; test if k painters can finish all boards in ≤ mid timehi = midlo = mid + 1The answer space is monotone: if k painters can finish in time T, they can also finish in time T+1. Binary search finds the smallest T where the answer flips from infeasible to feasible. The feasibility check is a simple greedy linear scan: assign boards to the current painter until adding the next board would exceed the time limit, then start a new painter. O(n log(sum)) total.
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.
Books, painters and ships are the same pattern. Binary search the busiest load, and check it greedily.
Run the animation above on your own input, or watch the 1:15 video explanation of The Painter's Partition Problem with a dry run and Java code.