Painters Partition Problem (With Solution)

Problem Statement

Given n paint boards, of length {a1, a2, …., an}, and k painters, find the minimum time to paint all the boards, such that any painter will paint only contiguous sections of paint boards. It may be assumed that each painter takes 1 unit of time to paint 1 unit of board.

Sample Test Cases

Input 1:

n = 6, k = 3

a = [10, 20, 60, 50, 30, 40]

Output 1:

90

Explanation 1:

It can be observed that if each worker is placed such that they are allowed to paint at most 90 units of length, then the work can be completed in a minimum time of 90 minutes by using k = 3 workers.

Input 2:

n = 4, k = 2,

a = [10, 20, 30, 40]

Output 2:

60

Explanation 2:

The first painter will paint board {10, 20, 30} and the 2nd painter will paint board {40}, taking a total time of 60 minutes. It can be observed that this partition is optimal.

Approach

Naive Approach:

The problem can be solved naively in a recursive manner. Observe, that if we have already placed k – 1 partitions, and we need a total of k partitions, then we can place the k – 1 th cut between the ith and (i + 1) th element where i lies in the range [1, n].

Now we need to compute the cost for this arrangement, which can be done as follows:

• Cost of the last partition, which is equal to getSum(i, n), where getSum represents the sum of the elements in the range [i, j],
• Maximum value of cost of any partition, which is formed to the left of the k – 1 th cut. 
• The cost for the arrangement will be the maximum of the above 2 cases.

To compute the value for 2nd point, we observe that it is itself a subproblem of the original problem with k := k – 1. So, our recursive code itself can this subproblem as the algorithm proceeds.

With the recurrence in place, we need to note our base case for the recursion which is as follows:

• For n = 1, Result = a[0].
• For k = 1, Result = getSum(1, n).

Code / Implementation:

C++ Code

int getSum(vector < int > & a, int left, int right) {
  int sum = 0;
  for (int i = left; i <= right; i++) {
    sum += a[i];
  }
  return sum;
}
int getMinimumTime(vector < int > & a, int n, int k) {
  if (n == 1) {
    return a[0];
  }
  if (k == 1) {
    return getSum(a, 0, n - 1);
  }
  int minimumTime = INT_MAX;
  for (int i = 1; i <= n; i++) {
    int partitionCost = max(getMinimumTime(a, i, k - 1), getSum(a, i, n - 1));
    minimumTime = min(minimumTime, partitionCost);
  }
  return minimumTime;
}

Java Code

public static int getSum(int[] a, int left, int right) {
  int sum = 0;
  for (int i = left; i <= right; i++) {
    sum += a[i];
  }
  return sum;
}
public static int getMinimumTime(int[] a, int n, int k) {
  if (n == 1) {
    return a[0];
  }
  if (k == 1) {
    return getSum(a, 0, n - 1);
  }
  int minimumTime = Integer.MAX_VALUE;
  for (int i = 1; i <= n; i++) {
    int partitionCost = Math.max(getMinimumTime(a, i, k - 1), getSum(a, i, n - 1));
    minimumTime = Math.min(minimumTime, partitionCost);
  }
  return minimumTime;
}

Python Code

def getSum(a, left, right):
    sum = 0
    for i in range(left, right + 1):
        sum += a[i]
    return sum


def getMinimumTime(a, n, k):
    if n == 1:
        return a[0]
    if k == 1:
        return getSum(a, 0, n - 1)
    minimumTime = 999999
    for i in range(1, n + 1):
        partitionCost = max(getMinimumTime(a, i, k - 1), getSum(a, i, n - 1))
        minimumTime = min(minimumTime, partitionCost)
    return minimumTime

Complexity Analysis:

• Time Complexity: Exponential
• Space Complexity: O(1) // If recursion stack space is ignored

Dynamic Programming Approach

Consider the partial recursion tree for n = 4, k = 3. We observe that many subproblems like (n, k) = (1, 1) are being repeatedly recalculated and redundantly resolved. For a larger recursion tree, even more such subproblems will solved for again and again. So, we can observe that this problem has some overlapping subproblems, as well as optimal substructure, which hints us that the problem can be solved with dynamic programming. The DP states are DP(i, j) represents computing the optimal cost for putting i partitions for the first j elements in the array. The answer can be found in DP(k, n). The transitions are the same as explained in the naive recursive approach. The getSum() function can also be optimized with the help of prefix sums.

Implementation:

C++ Code

int getSum(vector < int > & a, int left, int right) {
  if (left == 0) {
    return a[right];
  } else {
    return a[right] - a[left - 1];
  }
}
int getMinimumTime(vector < int > & a, int n, int k) {
  vector < int > pref(n);
  pref[0] = a[0];
  for (int i = 1; i < n; i++) {
    pref[i] = pref[i - 1] + a[i];
  }
  vector < vector < int >> dp(k + 1, vector < int > (n + 1, 0));
  for (int i = 1; i <= n; i++) {
    dp[1][i] = getSum(pref, 0, i - 1);
  }
  for (int i = 1; i <= k; i++) {
    dp[i][1] = a[0];
  }
  for (int i = 2; i <= k; i++) {
    for (int j = 2; j <= n; j++) {
      int minimumTime = INT_MAX;
      for (int cut = 1; cut <= j; cut++) {
        minimumTime = min(minimumTime, max(dp[i - 1][cut], getSum(pref, cut, j - 1)));
      }
      dp[i][j] = minimumTime;
    }
  }
  return dp[k][n];
}

Java Code

public static int getSum(int[] a, int left, int right) {
  if (left == 0) {
    return a[right];
  } else {
    return a[right] - a[left - 1];
  }
}
public static int getMinimumTime(int[] a, int n, int k) {
  int[] pref = new int[n];
  pref[0] = a[0];
  for (int i = 1; i < n; i++) {
    pref[i] = pref[i - 1] + a[i];
  }
  int[][] dp = new int[k + 1][n + 1];
  for (int i = 1; i <= n; i++) {
    dp[1][i] = getSum(pref, 0, i - 1);
  }
  for (int i = 1; i <= k; i++) {
    dp[i][1] = a[0];
  }
  for (int i = 2; i <= k; i++) {
    for (int j = 2; j <= n; j++) {
      int minimumTime = Integer.MAX_VALUE;
      for (int cut = 1; cut <= j; cut++) {
        minimumTime = Math.min(minimumTime, Math.max(dp[i - 1][cut], getSum(pref, cut, j - 1)));
      }
      dp[i][j] = minimumTime;
    }
  }
  return dp[k][n];
}

Python Code

def getSum(a, left, right):
    if left == 0:
        return a[right]
    else:
        return a[right] - a[left - 1]


def getMinimumTime(a, n, k):
    pref = [0] * n
    pref[0] = a[0]
    for i in range(1, n):
        pref[i] = pref[i - 1] + a[i]
    dp = [[0 for i in range(n + 1)] for j in range(k + 1)]
    for i in range(1, n + 1):
        dp[1][i] = getSum(pref, 0, i - 1)
    for i in range(1, k + 1):
        dp[i][1] = a[0]
    for i in range(2, k + 1):
        for j in range(2, n + 1):
            minimumTime = 999999
            for cut in range(1, j + 1):
                minimumTime = min(
                    minimumTime, max(dp[i - 1][cut], getSum(pref, cut, j - 1))
                )
            dp[i][j] = minimumTime
    return dp[k][n]

Complexity Analysis:

• Time Complexity: O(k * n * n)
• Space Complexity: O(k * n)

Binary Search Approach

We can also use binary search to solve this problem even optimally. The key idea here is use to binary search for the minimum amount of time which will allow us to completely paint the paint boards if we use the k painters optimally. 

How to move the pointers in the binary search?

• If the current mid is enough to paint the paint boards by k painters, we move the right pointer to mid-1. (The right half of the search space is eliminated)
• Else we move the left point to mid + 1. (The left half of the search space is omitted).
• The process is continued till the pointers meet or overtake each other.

How to check if k painters are enough for a particular mid?

• We can linearly traverse the array, and whenever a painter exceeds the total length of which he is allowed to paint, we assign the current paint board to the next painter in line.
• If all the paint boards can be coloured with this traversal, then the k painters are enough for the given mid-value, else not.

Implementation:

C++ Code

int getPainters(vector < int > & a, int n, int k) {
  int sum = 0, numberOfPainters = 1;
  for (auto x: a) {
    sum += x;
    if (sum > k) {
      sum = x;
      numberOfPainters++;
    }
  }
  return numberOfPainters;
}
int getMinimumTime(vector < int > & a, int n, int k) {
  int left = * max_element(a.begin(), a.end());
  int right = accumulate(a.begin(), a.end(), 0);
  int result = -1;
  while (left <= right) {
    int mid = (left + right) / 2;
    if (getPainters(a, n, mid) <= k) {
      result = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return result;
}

Java Code

public static int getPainters(int[] a, int n, int k) {
  int sum = 0, numberOfPainters = 1;
  for (int i = 0; i < n; i++) {
    int x = a[i];
    sum += x;
    if (sum > k) {
      sum = x;
      numberOfPainters++;
    }
  }
  return numberOfPainters;
}
public static int getMinimumTime(int[] a, int n, int k) {
  int left = 0, right = 0;
  for (int i = 0; i < n; i++) {
    left = Math.max(left, a[i]);
    right += a[i];
  }
  int result = -1;
  while (left <= right) {
    int mid = (left + right) / 2;
    if (getPainters(a, n, mid) <= k) {
      result = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
  }
  }
  return result;
}

Python Code

def getPainters(a, n, k):
    sum = 0
    numberOfPainters = 1
    for i in range(n):
        sum += a[i]
        if sum > k:
            sum = a[i]
            numberOfPainters += 1
    return numberOfPainters


def getMinimumTime(a, n, k):
    left = max(a)
    right = sum(a)
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if getPainters(a, n, mid) <= k:
            result = mid
            right = mid - 1
        else:
            left = mid + 1
    return result

Complexity Analysis:

• Time Complexity: O(n * log₂(sum(a)))
• Space Complexity: O(1)

Practice Problem:

• Allocate Books
• Painter’s Partition Problem

FAQs

Q.1: When should such binary search approaches be thought of?

Ans: Whenever, there is some pattern such that there is a point before and after which the nature of the curve changes, we can use binary search to search for that point.

Q.2: Which of the above approaches is optimal in terms of complexity analysis?

Ans: The binary search approach is optimal both in terms of Space and Time Complexity.