Create account

DEV Community

Rohith V

Posted on Jul 8, 2021

The Painter's Partition Problem

#algorithms #java #computerscience #programming

Problem Statement :

Dilpreet wants to paint his dog's home that has n boards with different lengths. The length of ith board is given by arr[i] where arr[] is an array of n integers. He hired k painters for this work and each painter takes 1 unit time to paint 1 unit of the board.

The problem is to find the minimum time to get this job done if all painters start together with the constraint that any painter will only paint continuous boards, say boards numbered {2,3,4} or only board {1} or nothing but not boards {2,4,5}.

Example Test Cases :

Input:

n = 5
k = 3
arr[] = {5,10,30,20,15}
Output: 35
Explanation: The most optimal way will be:
Painter 1 allocation : {5,10}
Painter 2 allocation : {30}
Painter 3 allocation : {20,15}
Job will be done when all painters finish
i.e. at time = max(5+10, 30, 20+15) = 35

Input:

n = 4
k = 2
arr[] = {10,20,30,40}
Output: 20

Approach :

Here at first we can think this problem like this.
Assume we have k - 1 partitions in place and have to put the k - 1th divider to get the k partitions.
How can we do this? We can put the k-1 th divider between the i th and i+1 th element where i = 1 to n. Please note that putting it before the first element is the same as putting it after the last element.
The total cost of this arrangement can be calculated as the maximum of the following:
a) The cost of the last partition: sum(Ai..An), where the k-1 th divider is
before element i.
b) The maximum cost of any partition already formed to the left of the k-1 th divider.
Here a) can be found out using a simple helper function to calculate sum
of elements between two indices in the array. How to find out b) ?
We can observe that b) actually is to place the k-2 separators as fairly as
possible, so it is a subproblem of the given problem. Thus we can write the optimal
substructure property as the following recurrence relation:

Note : Photo taken from geeksforgeeks

But for this approach we get exponential time complexity and the main idea is to use Binary search and optimising the complexity to nlogn

Approach Using Binary Search

We can see that the highest possible value in this range is the sum of all the elements in the array and this happens when we allot 1 painter all the sections of the board. The lowest possible value of this range is the maximum value of the array max, as in this allocation we can allot max to one painter and divide the other sections such that the cost of them is less than or equal to max and as close as possible to max. Now if we consider we use x painters in the above scenarios, it is obvious that as the value in the range increases, the value of x decreases and vice-versa. From this we can find the target value when x=k and use a helper function to find x, the minimum number of painters required when the maximum length of section a painter can paint is given.

Code :

class Solution{
    static long minTime(int[] arr,int n,int k){
        //code here
        long sum = getSum(arr);
        long max = getMax(arr);
        return binarySearch(arr, max, sum, k);
    }

    static long binarySearch(int [] arr, long low, long high, int k) {
        while (low < high) {
            long middle = low + (high - low) / 2;
            int painters = findPainters(arr, middle);
            if (painters <= k) {
                high = middle;
            }
            else {
                low = middle + 1;
            }
        }
        return low;
    }

    static int findPainters(int [] arr, long maxTime) {
        int painter = 1;
        long sum = 0;
        int length = arr.length;
        for (int i=0; i<length; i++) {
            sum += arr[i];
            if (sum > maxTime) {
                painter ++;
                sum = arr[i];
            }
        }
        return painter;
    } 

    static long getSum(int [] arr) {
        long total = 0;
        for (int number : arr) {
            total += number;
        }
        return total;
    }

    static long getMax(int [] arr) {
        long max = Integer.MIN_VALUE;
        for (int number : arr) {
            max = Math.max(max, number);
        }
        return max;
    }
}