Pattern visualizer
Painter's Partition Problem
There is no sorted list to search here, so search the ANSWER instead. Ask 'can 3 painters finish under a cap of X?' — and notice the answer is monotonic: if a cap works, every larger cap works too, and once a cap fails every smaller one fails. That yes/no boundary is exactly what binary search finds. Testing one cap is greedy and takes a single pass: pile boards onto the current painter until the next board would break the cap, then hand the brush over. Greedy is safe because stopping a painter early never lets a later painter do less. Animated on: boards = 5, 10, 30, 20, 15, 25, 10, 5 and 3 painters, each painting a run of neighbouring boards at one unit per second — find the earliest moment all boards are done..
Binary search the ANSWER, then greedily test it
8 boards 5, 10, 30, 20, 15, 25, 10, 5 and 3 painters, each taking a run of neighbouring boards. The clock stops when the SLOWEST painter finishes, so we hunt the smallest possible workload for the busiest one. One painter doing everything costs 120; the longest single board, 30, is unavoidable — so the answer lives between 30 and 120.
1FUNCTION minTime(boards, k):2 low <- MAX(boards)3 high <- SUM(boards)4 WHILE low <= high5 mid <- (low + high) / 26 IF paintersNeeded(boards, mid) <= k7 best <- mid8 high <- mid - 19 ELSE10 low <- mid + 111 RETURN best
← / → step · space play · Home restart