DSA Tracker

Visualize

The Painter's Partition Problem-II

Binary search the ANSWER, then greedily test it

time O(n log(sum(boards)))space O(1)

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.

Details

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.

Problem:The Painter's Partition Problem-IIHard

Binary search the ANSWER, then greedily test it

step 1 / 9

5
[0]
10
[1]
30
[2]
20
[3]
15
[4]
25
[5]
10
[6]
5
[7]

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.

Pseudocode
1FUNCTION minTime(boards, k):
2  low <- MAX(boards)
3  high <- SUM(boards)
4  WHILE low <= high
5    mid <- (low + high) / 2
6    IF paintersNeeded(boards, mid) <= k
7      best <- mid
8      high <- mid - 1
9    ELSE
10      low <- mid + 1
11  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. 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.
  2. Try a cap of 75. Filling each painter as far as the cap allows splits the boards into 5+10+30+20=65 | 15+25+10+5=55 — only 2 runs, and we have 3 painters, so 75 is achievable. Bank it and squeeze the cap DOWN: high becomes 74.
  3. Try a cap of 52. Filling each painter as far as the cap allows splits the boards into 5+10+30=45 | 20+15=35 | 25+10+5=40 — only 3 runs, and we have 3 painters, so 52 is achievable. Bank it and squeeze the cap DOWN: high becomes 51.
  4. Try a cap of 40. Greedily filled it takes 5+10=15 | 30=30 | 20+15=35 | 25+10+5=40 — 4 runs for 3 painters, so 25, 10, 5 would be left with nobody to paint them. The cap is too tight: low becomes 41.
  5. Try a cap of 46. Filling each painter as far as the cap allows splits the boards into 5+10+30=45 | 20+15=35 | 25+10+5=40 — only 3 runs, and we have 3 painters, so 46 is achievable. Bank it and squeeze the cap DOWN: high becomes 45.
  6. Try a cap of 43. Greedily filled it takes 5+10=15 | 30=30 | 20+15=35 | 25+10+5=40 — 4 runs for 3 painters, so 25, 10, 5 would be left with nobody to paint them. The cap is too tight: low becomes 44.
  7. Try a cap of 44. Greedily filled it takes 5+10=15 | 30=30 | 20+15=35 | 25+10+5=40 — 4 runs for 3 painters, so 25, 10, 5 would be left with nobody to paint them. The cap is too tight: low becomes 45.
  8. Try a cap of 45. Filling each painter as far as the cap allows splits the boards into 5+10+30=45 | 20+15=35 | 25+10+5=40 — only 3 runs, and we have 3 painters, so 45 is achievable. Bank it and squeeze the cap DOWN: high becomes 44.
  9. low 45 has passed high 44, so every cap has been decided. 45 is the smallest one that still fits 3 painters: 5+10+30=45 | 20+15=35 | 25+10+5=40. Shave a single unit off it and the greedy fill needs a 4th painter, so 45 is the finish time.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve The Painter's Partition Problem-II in the editorAll Binary Search problemsBack to roadmap