Assign Wall Boards to Painters to Minimize the Slowest Painter's Time
Solve this Problemboards[i] units of length each — must be assigned to k painters, each getting a contiguous run of boards (never splitting one, and every painter must get at least one). Every painter paints at the same fixed rate: timePerUnit time units per unit of length. Find the assignment that minimizes the slowest painter's total time, and return that minimized time.
Since every painter shares the same rate, comparing painters by their assigned length gives exactly the same ordering as comparing them by time — so the search can work entirely in length units, and only multiply by timePerUnit once, at the very end, instead of repeating the conversion for every candidate.
No length limit below the single longest board could ever work, and a limit equal to the wall's total length always needs just one painter — so the answer is guaranteed to fall somewhere between those two bounds. The number of painters needed only ever decreases (or stays flat) as the length limit grows, which makes this a binary search on the answerBinary Search on the AnswerInstead of searching a sorted array, the search runs directly over the space of possible answers (here, every candidate length limit). It works whenever "is this candidate good enough?" is monotonic — once a candidate works, every larger candidate keeps working too. — search directly over candidate length limits rather than trying every possible way to split the boards.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of boards ≤ 1000 - ◆
1 ≤ boards[i] ≤ 1000 (units of length) - ◆
1 ≤ k ≤ number of boards - ◆
1 ≤ timePerUnit ≤ 100
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Length Limit From the Longest Board Upward
BruteBoards must be assigned in order, never splitting one, and a painter's assignment keeps growing until the next board would push their total length over some limit — at which point a new painter takes over. Every painter works at the same fixed rate, so the slowest painter's time is simply their assigned length times timePerUnit. No length limit below the single longest board could ever work, and a limit equal to the total board length always needs just one painter — so the true limit lies between those two bounds. Try every limit in that range, in order, counting how many painters it needs; the first limit that fits within k painters gives the answer (after multiplying by timePerUnit). Correct, but scanning every candidate limit one at a time wastes a lot of work.
O(n · (sum − max))O(1)1class Solution {
2 public int minPaintTime(int[] boards, int k, int timePerUnit) {
3 int maxB = 0, sum = 0;
4 for (int b : boards) { maxB = Math.max(maxB, b); sum += b; }
5 for (int cap = maxB; cap <= sum; cap++) {
6 if (groupsNeeded(boards, cap) <= k) return cap * timePerUnit;
7 }
8 return sum * timePerUnit;
9 }
10
11 private int groupsNeeded(int[] boards, int cap) {
12 int groups = 1, length = 0;
13 for (int b : boards) {
14 if (length + b > cap) { groups++; length = 0; }
15 length += b;
16 }
17 return groups;
18 }
19}Optimal — Binary Search on the Length Limit
OptimalThe number of painters needed only ever goes down (or stays the same) as the length limit grows — a bigger limit can never need more painters. That monotonic relationship is exactly what binary search needs: search the candidate length limits between the longest single board and the total board length, and whenever a candidate limit fits within k painters, remember it and try a smaller limit; otherwise it's too tight, so search bigger. Once the smallest feasible length limit is found, multiply it by timePerUnit for the final time.
O(n · log(sum − max))O(1)1class Solution {
2 public int minPaintTime(int[] boards, int k, int timePerUnit) {
3 int lo = 0, hi = 0;
4 for (int b : boards) { lo = Math.max(lo, b); hi += b; }
5 int ans = hi;
6 while (lo <= hi) {
7 int mid = lo + (hi - lo) / 2;
8 if (groupsNeeded(boards, mid) <= k) {
9 ans = mid;
10 hi = mid - 1;
11 } else {
12 lo = mid + 1;
13 }
14 }
15 return ans * timePerUnit;
16 }
17
18 private int groupsNeeded(int[] boards, int cap) {
19 int groups = 1, length = 0;
20 for (int b : boards) {
21 if (length + b > cap) { groups++; length = 0; }
22 length += b;
23 }
24 return groups;
25 }
26}