You have to paint n boards of length {L1, L2, L3,…,Ln-1}. There are k painters available and each painter takes t time to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will paint only contiguous sections of boards.
- 2 painters cannot share a board to paint. That is to say, a board cannot be painted partially by one painter, and partially by another.
- A painter will paint only contiguous boards. Which means a configuration where a painter paints board 1 and 3 but not 2 is invalid.
Find out minimum time to paint all boards?
Examples:
Input : k = 2, t = 5, L = [1,10] Output : 50
Solution-
A simple observation-
- If the job can be done in time T, then it can also be done in any time>=T.
- If the job cannot be done in time T, then in cannot be done in any time<=T.
Clearly, we could use binary search to find the answer. But we need to find the sample space first. The starting point can be 0, and ending point can be time to paint all the boards by a single painter i.e. t*(sum of length of all boards) Now we need to have a function which could tell if it is possible to paint all boards in maximum time T. Here is an algorithm for same-
- Initialize sum = 0, count_painter = 1 and traverse the array L
- If L[i]*t + sum > T , it means we cannot make our current painter paint current boards as it will exceed maximum time. So we need to increase the count_painter and reinitialize sum i.e. count_painter++ and sum=0. Don’t increment i in this case.
Else, it means we can make our current painter to paint current board and it will not exceed time limit. So we just add it to our current sum i.e. sum += L[i]*t - After traversal if the count_painter <= k then it is possible to complete the job in time T else not.
Below is a JAVA code for above problem-
import java.util.ArrayList;
public class Solution {
public int paint(int k, int t, ArrayList<Integer> L) {
long start = 0, end = 0, mid = 0, ans = Long.MAX_VALUE, max_length = -1;
for (Integer x : L) {
end += x; // ending point as the sum of the length of all boards
max_length = Math.max(max_length, x); // maximum length of boards
}
while (start <= end) {
mid = start + (end - start) / 2;
if (isPossible(L, k, mid, max_length)) {
ans = Math.min(ans, mid);
end = mid - 1; // if it is possible that no painter paints more than mid boards then
// it is also possible that no painter paints more than x boards where x > mid
} else {
// if it is not possible that no painter paints more than mid boards then for any lesser
// value of mid it is also not possible
start = mid + 1;
}
}
return (int) (ans * t); // multiply back the time factor
}
public boolean isPossible(ArrayList<Integer> l, int n, long max_boards, long max_length) {
if (max_length > max_boards) // if there is a board with greater length than max length allowed
return false;
long sum = 0;
int count = 1;
for (int i = 0; i < l.size();) {
if ((sum + l.get(i)) > max_boards) {
// current painter cannot paint the current board as it will cross the threshold
// hence we need a new painter
sum = 0;
count++;
} else {
// current painter can paint the current board, and it won't cross the threshold
sum += l.get(i);
i++;
}
}
// check if the number of painters required are available
return count <= n;
}
public static void main(String[] args) {
ArrayList<Integer> L = new ArrayList<>();
L.add(1);
L.add(10);
int k = 2, t = 5;
System.out.println("Minimum time required = " + new Solution().paint(k, t, L));
}
}
Output:
Minumum time required = 50
Note that upon more observation we find that t is just a multiplying time factor and we can change our statement of binary search to be – No painter paints more than X boards. This statement will also ensure that overflow doesn’t happen because of t. You may practise similar questions here-