dsa · medium

Painter's Partition

GreyOrangeBinary SearchGreedy

boards[i] is the time to paint board i (one unit per time). k painters work in parallel, each taking a **contiguous** segment. Return the minimum time to paint all boards.

Arguments

• boards — board lengths / paint times
• k — how many painters work in parallel (each paints one contiguous segment)

Naukri GreyOrange pack. Binary search on the answer + greedy check.

**Example:** boards=[10,20,30,40], k=2 → 60.

Constraints

1 <= k <= len(boards) <= 1000 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[10,20,30,40]
2

Expected:
60

Open in the Dojo editor