Problem of the day
Given an array/list of length ‘n’, where the array/list represents the boards and each element of the given array/list represents the length of each board. Some ‘k’ numbers of painters are available to paint these boards. Consider that each unit of a board takes 1 unit of time to paint.
You are supposed to return the area of the minimum time to get this job done of painting all the ‘n’ boards under a constraint that any painter will only paint the continuous sections of boards.
Input: arr = [2, 1, 5, 6, 2, 3], k = 2
Output: 11
Explanation:
First painter can paint boards 1 to 3 in 8 units of time and the second painter can paint boards 4-6 in 11 units of time. Thus both painters will paint all the boards in max(8,11) = 11 units of time. It can be shown that all the boards can't be painted in less than 11 units of time.
The first line contains two integers ‘n’ and ‘k’ denoting the number of elements in the array/list and number of painters available.
The second line contains ‘n’ single space-separated integers denoting the elements of the array/list.
Return the minimum time required to get the job done.
You do not need to print anything; it has already been taken care of.
4 2
10 20 30 40
60
In this test case, we can divide the first 3 boards for one painter and the last board for the second painter.
2 2
48 90
90
Try to do this in O(n*log(n)).
1 <= n <= 10^5
1 <= k <= n
1 <= arr[i] <= 10^9
Time Limit: 1 sec.
Divide the boards into k of fewer partitions such that the maximum sum of the elements in a partition, overall partitions is minimized.
All we need to do is to Divide the boards into k of fewer partitions such that the maximum sum of the elements in a partition, overall partitions is minimized.
We can put the (k - 1)th divider between the ith and (i + 1)th element where i is between 1 and N.
Now the recursive function will just require two conditions that can lead to the result and that will be out the maximum total cost:
Now to avoid the exponential time complexity we can use Dynamic Programming since it already keeps a track of pre-calculated data and will lead to better results if we can take the data from the dp table.
O(K * N ^ 3), where ‘N’ is the number of elements in the given array/list and ‘K’ is the number of painters available.
We are considering K painters and for each painter, it takes N ^ 3 iterations to calculate the minimum time for each number of painters. So the overall time complexity will be O(K * N ^ 3).
O(K * N), where ‘N’ is the number of elements in the given array/list and ‘K’ is the number of painters available.
Since we are creating a dp table of size (N + 1) * (K + 1), the overall space complexity will be O(N * K).