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.

Return the ans % 10000003

Input :
K : Number of painters
T : Time taken by painter to paint 1 unit of board
L : A List which will represent length of each board


Output:
     return minimum time to paint all boards % 10000003
Example

Input : 
  K : 2
  T : 5
  L : [1, 10]

Output : 50
Method1

This question is the same as Allocate Books

We can use DP. dp[k][n] = min( max(dp[k - 1][j], sum(j, n)) ) for 1 < j < n

Solution:

Time: O(k * n ^ 2)
Space: O(k * n)

public class Solution {
    public int paint(int A, int B, ArrayList<Integer> C) {
        List<Integer> list = C;
        long minMaxTime = paritition(list, A);
        return (int) ((minMaxTime * B) % 10000003);
    }
    
    private long sum(List<Integer> list, int from, int to) {
        long sum = 0;
        for (int i = from; i <= to; i ++) {
            sum += list.get(i);
        }
        return sum;
    }
    // dp[k][n] = min( max(dp[k - 1][j], sum(j, n)) ) for 1 < j < n
    private long paritition(List<Integer> list, int k) {
        int n = list.size();
        long[][] dp = new long[k + 1][n + 1];
        // k = 1
        for (int i = 1; i <= n; i ++) {
            dp[1][i] = sum(list, 0, i - 1);
        }
        // n = 1
        for (int i = 1; i <= k; i ++) {
            dp[i][1] = list.get(0);
        }
        for (int i = 2; i <= k; i ++) {
            for (int j = 2; j <= n; j ++) {
                long minTime = Long.MAX_VALUE;
                for (int p = 1; p < j; p ++) {
                    minTime = Math.min(minTime, Math.max(dp[i - 1][p], sum(list, p, j - 1)));
                }
                dp[i][j] = minTime;
            }
        }
        return dp[k][n];
    }
}

Method2

Binary Search

Solution:

Time: O(nlog(sum(L)))
Space: O(1)

public class Solution {
    public int paint(int A, int B, ArrayList<Integer> C) {
        List<Integer> list = C;
        long minMaxTime = paritition(list, A);
        return (int) ((minMaxTime * B) % 10000003);
    }
    
    private long sum(List<Integer> list, int from, int to) {
        long sum = 0;
        for (int i = from; i <= to; i ++) {
            sum += list.get(i);
        }
        return sum;
    }
    
    private long max(List<Integer> list) {
        long max = (long) list.get(0);
        for (int i = 1; i < list.size(); i ++) {
            max = Math.max(max, (long) list.get(i));
        }
        return max;
    }
    
    private int numberOfPainters(List<Integer> list, long maxLength) {
        int number = 1;
        int currLength = 0;
        for (int i = 0; i < list.size(); i ++) {
            currLength += list.get(i);
            if (currLength > maxLength) {
                number ++;
                currLength = list.get(i);
            }
        }
        return number;
    }

    private long paritition(List<Integer> list, int k) {
        int n = list.size();
        long left = max(list);
        long right = sum(list, 0, n - 1);
        while (left <= right) {
            long mid = left + (right - left) / 2;
            // System.out.println("left: " + left);
            // System.out.println("right: " + right);
            // System.out.println("mid: " + mid);
            // System.out.println("workers: " + numberOfPainters(list, mid));
            if (numberOfPainters(list, mid) <= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}