Painter's Partition Problem
HardP2Coding
There are boards.length boards; boards[i] is the length of board i. You have k painters. A painter paints one unit of board length per unit of time, and each painter paints a contiguous block of boards (possibly none). A board cannot be split between painters.
Return the minimum time needed to paint all the boards, where the time is the largest total length any single painter gets.
Example 1
- Input
- boards = [10,20,30,40], k = 2
- Output
- 60
- Why
- Painter 1: 10+20+30 = 60, painter 2: 40.
Example 2
- Input
- boards = [5,5,5], k = 3
- Output
- 5
Example 3
- Input
- boards = [7], k = 4
- Output
- 7
Constraints
- 1 <= boards.length <= 10^5
- 1 <= k <= 10^5
- 1 <= boards[i] <= 10^4
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 11. ⌘Enter runs, ⌘⇧Enter submits.