The Painter's Partition Problem

Interview

Description:

You have to paint N boards of lenght {A0, A1, A2 ... 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 continues sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

Example:

Note

Idea:

就是一个数组，切成k份，怎么让max of每一份的sum最小。

Method 1, DP:

We define M[n, k] as the optimum cost of a partition arrangement with n total blocks from the first block and k patitions, so

                 n              n-1
M[n, k] = min { max { M[j, k-1], ∑ Ai } }
                j=1             i=j
The base cases are:

M[1, k] = A0
         n-1
M[n, 1] = Σ Ai
         i=0

http://www.cnblogs.com/litao-tech/p/4175401.html

Method 2, trick:

Code:

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <utility>
#include <memory>
#include <cmath>

using namespace std;

// Method 1
// Time: O(n*k*n)
// Space: O(n*k)
int painterDP(const vector<int> & input, int start, int num_seg, vector<vector<int>>& DP){
    if(DP[start][num_seg]!=INT_MIN) return DP[start][num_seg];

    // cout<<"level "<<start<<' '<<num_seg<<endl;

    int end=input.size();

    // need k segments, but only remain k vector elements, pick the largest value
    int localMax=INT_MIN;
    if((end-start)==num_seg){
        for(int i=start; i<end; ++i){
            localMax= input[i]>localMax ? input[i] : localMax;
        }
        DP[start][num_seg]=localMax;
        return localMax;
    }

    // need 1 segment, pick the sum value
    if(num_seg==1){
        int localsum=0;
        for(int i=start; i<end; ++i){
            localsum += input[i];
        }
        DP[start][num_seg]=localsum;
        return localsum;
    }

    // Else, DP
    int subMin=INT_MAX;
    int leftsum=0;
    for(int i=start; i<= end-num_seg; ++i){
        leftsum += input[i];
        localMax = max(leftsum, painterDP(input, i+1, num_seg-1, DP));
        if(localMax<subMin)
            subMin=localMax;
    }
    DP[start][num_seg]=subMin;
    return subMin;

}

int painterDP(const vector<int> & input, int k){
    int n=input.size();
    vector<vector<int>> DP(n, vector<int>(k+1, INT_MIN));

    return painterDP(input, 0, k, DP);
}

// Method 2
// Time: O(n*log(sum of input)), no Space

int getMax(const vector<int> & input){
    if(input.empty()) return INT_MIN;
    int max_val=input[0];
    for(int i=1; i<input.size(); ++i){
        if(max_val<input[i]) max_val=input[i];
    }
    return max_val;
}

// If the max sum limit is given, how many segments are there?
int getNumPainter(const vector<int> & input, int val_limit){
    int seg_sum=0;
    int count=1;

    for(int i=0; i<input.size(); ++i){
        if(seg_sum+input[i] <= val_limit){
            seg_sum += input[i];
        }
        else{
            count++;
            seg_sum=input[i];
        }
    }

    return count;
}


int painterBinarySearch(const vector<int> & input, int k){
    int low=getMax(input);
    int high=accumulate(input.begin(), input.end(), 0);

    while(low<high){
        int mid = low + (high-low)/2;
        int num_painter = getNumPainter(input, mid);
        if(num_painter > k){
            low=mid+1;
        }
        else{
            high=mid;
        }
    }

    return low;
}

// Method 3, This simple merge neighboring elements method is WRONG!
// Time: O(n*(n-k))

int painterMerge(const vector<int> & input, int k){
    if(k==1) return accumulate(input.begin(), input.end(), 0);

    vector<int> segments(input.begin(), input.end());

    for(int curr_k=input.size(); curr_k>k; curr_k--){

        auto it_1=segments.begin();
        auto it_2=segments.begin()+1;
        int min_two=*it_1 + *it_2;

        for(auto it=segments.begin(); it<segments.end()-1; it++){
            if(min_two > (*it + *(it+1))){
                it_1=it;
                it_2=it+1;
            }
        }
        *it_2 = *it_2 + *it_1;
        segments.erase(it_1);
    }

    int max_segment=0;
    for(auto e: segments){
        if(max_segment < e) max_segment = e;
    }

    return max_segment;
}

int main(){
    int k=5;
    vector<int> input={10,2,1,3,4,5,5,2,6,7,8,2};
    // int k=2;
    // vector<int> input={10,1,2,9};


    cout<<painterMerge(input, k)<<endl; // This gives wrong answer.
    cout<<painterDP(input, k)<<endl;
    cout<<painterBinarySearch(input, k)<<endl;
}