Painter's Partition Problem

题目描述

You have to paint N boards of length {A0, A1, A2, A3 … AN-1}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint contiguous sections of board.

A - number of painters
B - 
C - LIst of board length

注意是要continuous assign，这是一个非常重要的条件。

解题方法

recursion

Recursion can be utilized to solve this problem easily. Imagine that we already have (k-1) partitions in place (the left partition) and we are trying to put the last separator (the (k-1)th separator). What are the possible locations to put the last separator? It must lie somewhere between the (j-1)th and jth element, where 1 = j = n. Once we have the last separator in place, we have completed all k partitions.

def sum(C, start, end):


def partition(A, B, C):
    if A == 1:
        return sum(C, 0, len(C))
    if len(C) == 1:
        return C[0]
    best = sys.maxint
    for i in range(1, len(C)+1):
        best = min(best, max(partition(A-1, B, C[:i]), sum(C, i, len(C))))

    return best

DP

可以将recursive的方法改进为DP的方法

def findMax(A, B, k):
    length = len(A)
    # row - num of boards
    # col - num of painters
    DP = [[0 for i in range(k+1)] for j in range(length+1)]

    cum = [0 for i in range(length+1)]
    for i in range(1, length+1):
        cum[i] = cum[i-1] + A[i-1]

    for i in range(1, length+1):
        DP[i][1] = cum[i]
    for i in range(1, k+1):
        DP[1][i] = A[0]

    for i in range(2, k+1):
        for j in range(2, length+1):
            best = sys.maxint
            for p in range(1, j+1):
                best = min(best, max(M[p][i-1], cum[j] - cum[p]))
            DP[i][j] = best

    return DP[length][k]

二分法

我们将每个painter分配到的max load设为max_per_painter

  • max_per_painter的下限是max(C), 因为至少要能够画最长的那块板
  • max_per_painter的上限是sum(C)

可以利用二分法，不断地找到中点，求出该中点需要的painter的数量，跟限制数量 B比较，然后进行二分。

优化

我们知道C是递增的，肯定会在C的开头选取一些连续的作为第一个painter的工作量， 所以我们可以先生存一个C的cumulative sum的array,设为sum[], 找到一个index i

  • sum[i]为max_per_painter的时候不满足数量要求
  • sum[i+1]为max_per_painter的时候满足数量要求

这样就可以把max_per_painter的范围限制到sum[i] - sum[i+1]

Solution

class Solution:
    # @param A : integer
    # @param B : integer
    # @param C : list of integers
    # @return an integer
    def paint(self, A, B, C):
        start = max(C)
        end = sum(C)

        while start + 1 < end:
            mid = start + (end-start)/2
            required_num = self.getRequiredPainters(C, mid)
            if required_num <= A:
                end = mid
            else:
                start = mid + 1
        if self.getRequiredPainters(C, start) <= A:
            return B * start % 10000003
        else:
            return B * end % 10000003

    def getRequiredPainters(self, l, max_per_painter):
        cur_total = 0
        num_painter = 1
        for i in range(len(l)):
            cur_total += l[i]
            if cur_total > max_per_painter:
                cur_total = l[i]
                num_painter += 1
        return num_painter

Reference