Painters Partition

Problem

Given board lengths and k painters, return the minimum possible time for k painters to paint all boards, where each painter paints a contiguous segment and the finish time is the largest segment sum. Return -1 when k < 1.

Binary search the answer between the longest board and the total length, checking feasibility by greedily counting how many painters a candidate limit requires.

Hint

A limit is feasible when the greedy painter count does not exceed k.

Test cases

case 1

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

expected: 60

case 2

in: [[10,20,30,40],1]

expected: 100

case 3

in: [[10,20,30,40],4]

expected: 40

case 4

in: [[5],1]

expected: 5

case 5

in: [[1,2,3,4,5],3]

expected: 6

Starter codePython

def painters_partition(boards, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor