The Painter's Partition Problem Python

PROGRAM TO SOLVE THE PAINTER'S PARTITION PROBLEM

We have to paint n boards of length {A1, A2, .. An}. There are k painters available and each takes 1 unit time to paint 1 unit of board. The problem is to find the minimum time to get this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}. Example:

Input : k = 2, A = {10, 10, 10, 10} 
Output : 20.
Here we can divide the boards into 2
equal sized partitions, so each painter 
gets 20 units of board and the total
time taken is 20. 

# Find minimum required painters for given maxlen

# which is the maximum length a painter can paint

def numberOfPainters(arr, n, maxLen):

    total = 0

    numPainters = 1

  

    for i in arr:

        total += i

  

        if (total > maxLen):

  

            # for next count

            total = i

            numPainters += 1

  

    return numPainters

  

def partition(arr, n, k):

    lo = max(arr)

    hi = sum(arr)

  

    while (lo < hi):

        mid = lo + (hi - lo) / 2

        requiredPainters = numberOfPainters(arr, n, mid)

  

        # find better optimum in lower half

        # here mid is included because we

        # may not get anything better

        if (requiredPainters <= k):

            hi = mid

  

        # find better optimum in upper half

        # here mid is excluded because it gives 

        # required Painters > k, which is invalid

        else:

            lo = mid + 1

  

    # required

    return lo

  

# Driver code

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]

n = len(arr)

k = 3

print(int(partition(arr, n, k)))




OUTPUT

17

CREDITS: https://www.geeksforgeeks.org/painters-partition-problem-set-2/