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 * log2(sum(a)))
- Space Complexity: O(1)
Practice 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.
