Painter Load Balance Problem

Painter Load Balance Problem — ExecCode Hard DSA Practice

Solve the Painter Load Balance problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A fence of n boards with positive lengths must be painted by exactly k painters. Each painter gets a contiguous block. You want to minimize the maximum load (sum of one painter's boards). Binary search the load and greedily check; the same recurrence is divide-and-conquer DP-optimizable. Return that minimized maximum block sum. If k exceeds n, each board can have its own painter, so the answer is max(arr). You are given: arr — positive board lengths k — number of painters Return minimum possible maximum load. Painters cannot skip a board in the middle of their block.

Examples

Input {'arr': [7, 2, 5, 10], 'k': 2}; Output 14. Input {'arr': [3, 3, 3], 'k': 3}; Output 3. Input {'arr': [8], 'k': 1}; Output 8

Constraints

Boards stay in order k >= 1

Practice Painter Load Balance free on ExecCode. Browse DSA problems, topic map, and placement guides.