Painter's Partition
MediumMinimize the slowest painter
Guess how long the painters get; if they finish the fence in that time try faster, otherwise slower.
The idea
k painters paint contiguous boards; a bigger time budget needs fewer painters. Binary search the least time that fits within k painters.
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
candidates16
Step 1 of 3. Brute force: try every page-limit until the books fit 2 students. Values: 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30. candidates 16.
1/3
Brute force
timeO(sum·n)spaceO(1)
Try every limit.
1let best = -1;2for (let cap = maxBoard; cap <= sum && best < 0; cap++)3 if (paintersNeeded(cap) <= painters) best = cap;4return best;Input
- array
- [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, …]
Memory
- try
- —
- candidates
- 16
Output
- limit
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- pages = [12, 34, 67, 90], students = 2
- Output:
- 113
- Explanation:
- Split so the busiest student reads 113 pages.
Example 2
- Input:
- pages = [25, 46, 28, 49, 24], students = 4
- Output:
- 71
- Explanation:
- Fairest max load is 71.
Example 3
- Input:
- pages = [5, 17, 100, 11], students = 4
- Output:
- 100
- Explanation:
- One book of 100 forces max 100.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.