Painter's Partition Problem

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
586 upvotes
Asked in companies
OYOHSBCPayPal

Problem statement

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.


Example :
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.


Detailed explanation ( Input/output format, Notes, Images )
Input format :
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.


Output format :
Return the minimum time required to get the job done.


Note :
You do not need to print anything; it has already been taken care of.
Sample Input 1 :
4 2
10 20 30 40


Sample Output 1 :
60


Explanation For Sample Input 1 :
In this test case, we can divide the first 3 boards for one painter and the last board for the second painter.


Sample Input 2 :
2 2
48 90


Sample Output 2 :
90


Expected Time Complexity:
Try to do this in O(n*log(n)).


Constraints :
1 <= n <= 10^5
1 <= k <= n
1 <= arr[i] <= 10^9

Time Limit: 1 sec.
Hint

Divide the boards into k of fewer partitions such that the maximum sum of the elements in a partition, overall partitions is minimized.

Approaches (3)
Dynamic Programming

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:

  • The time is taken in the last partition where the (k - 1)th divider is before element i.
  • The maximum cost of any partition already formed to the left of the (k - 1)th divider.

 

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.

 

Time Complexity

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).

Space Complexity

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).

Code Solution
(100% EXP penalty)
Painter's Partition Problem
Full screen
Console