Interview Questions/Coding/Batch Paint Deadline Split

Batch Paint Deadline Split

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Batch Paint Deadline Split

A manufacturing line has boards in a fixed order. Several painters work in parallel, and each painter must receive one contiguous block of boards. A board cannot be split between painters, and the order of boards cannot be changed. The workload of a painter is the sum of board lengths assigned to that painter. The goal is to minimize the maximum workload assigned to any painter. Input Format: You are given an integer array boards and an integer painters. Output Format: Return the minimum possible maximum painter workload.

Examples

Example 1

Input:

boards = [10, 20, 30, 40]
painters = 2

Output:

Explanation: With limit 60, the boards can be split as [10, 20, 30]=60 and [40]=40, using 2 painter(s). Limit 59 would need 3 painter(s), so 60 is minimal.

Approach hint

The answer is between the largest board and total board length.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp