Painting Boards with a Limit per Painter
Updated
Problem statement
A row of boards must be painted. boards[i] is the number of minutes board i takes. There are k painters, and they all start at the same time.
Each painter paints one unbroken run of neighboring boards, and every board is painted by exactly one painter. A painter may also paint nothing. A painter's working time is the sum of the minutes of their boards. One extra rule: a painter may paint at most maxBoards boards.
The job is done when the busiest painter finishes. Return the smallest possible time for the job.
Function
minPaintTime(boards: int[], k: int, maxBoards: int) → intExamples
Example 1
boards = [3,1,2,1,9,8]k = 3maxBoards = 3return = 10One plan: the first painter takes 3, 1, 2 (6 minutes), the second takes 1, 9 (10 minutes), the third takes 8. The busiest painter needs 10 minutes. To finish in 9, the 9 cannot share a painter with the 1 before it (10) or the 8 after it (17), so 9 and 8 need one painter each. That leaves 3, 1, 2, 1 for the third painter: 4 boards, more than the limit of 3. So 9 needs a fourth painter. Without the 3-board limit, 3, 1, 2, 1 / 9 / 8 would give 9.
Example 2
boards = [6,2,4,7,1]k = 2maxBoards = 5return = 12The limit of 5 boards never matters here. Splitting as 6, 2, 4 / 7, 1 gives 12 and 8, so the answer is 12. To finish in 11 or less, the first painter could take only 6, 2 (adding 4 makes 12), leaving 4, 7, 1 = 12 for the second.
Example 3
boards = [10,1,1,1,1,1,1]k = 2maxBoards = 4return = 12The second painter can take at most 4 boards, so the first painter must take at least 3: 10, 1, 1 = 12 minutes. The other 4 boards take 4 minutes. The answer is 12, not the 10 you would get without the limit.
Constraints
1 <= boards.length <= 100001 <= boards[i] <= 1000001 <= k <= boards.length1 <= maxBoards <= boards.lengthk * maxBoards >= boards.length, so every board can be painted.
More Rippling Online Assessment questions
- Most Segments That Sort the ArrayOA · Seen Nov 2026
- Palindromic Paths to the RootOA · Seen Nov 2026
- Server InvestmentOA · Seen Nov 2026
- Corporate Card Expense RulesOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- REST API: Highest International StudentsOA · Seen Sep 2026
- Token ValidationOA · Seen Sep 2026
- Consistent LogsOA · Seen Sep 2026
- Costliest ChocolateOA · Seen Sep 2026
- Server ManagementOA · Seen Sep 2026
- Cyber Beacon DetectionOA · Seen Aug 2026
Similar questions at other companies
- Capacity to Ship Packages Within DaysMicrosoft · OA · ONSITE INTERVIEWMicrosoft interview questions
- Rock JumpingIMC Trading · OAIMC Trading interview questions
- Minimum Robot and Human Fulfillment TimeAmazon · OA
- Minimize Maximum Group DifferenceDRW · OADRW interview questions
- Array NullificationQRT · OA
- Minimum-Cost Solar Rooftop AllocationDeloitte · OADeloitte interview questions
- Three-Part Partition with Minimum Largest RangeLSEG · OALSEG interview questions
- K-Means ClusteringAtlassian · OAAtlassian interview questions
- Get Minimum Development TimeSalesforce · OASalesforce interview questions
- Job ExecutionMathWorks · OAMathWorks interview questions
Interview reports that mention this question
Rippling interview experiences
- Rippling No-Level Older Reports: 31 Experiences (Part 6 of 6)
- Rippling No-Level Onsite Loops: 24 Experiences (Part 5 of 6)
- Rippling No-Level Screens and Loops: 18 Experiences (Part 4 of 6)
- Rippling No-Level Coding Screens: 37 Experiences (Part 3 of 6)
- Rippling No-Level Design, Screens: 30 Experiences (Part 2 of 6)