Painters Partition Problem

In Painters Partition problem, we have M boards of length {l1, l2,... lm} to paint, and there are N painters available. In Painters Partition, each painter takes one unit of time to paint one unit of the board.

Calculate the minimum amount of time to complete this task while keeping in mind that any painter will only paint contiguous sections of the board.

The board cannot be painted partially by one painter and partially by another, which means they cannot share the board to paint.
Every painter will paint the contiguous board, which means that if the painter paints boards 1 and 3 but not 2, the painting is invalid.

Scope

This article tells about painters partition problem.

In this article we will learn to solve the painters partition problem using brute force approach.

In this article we will learn to solve the painters partition problem using binary search .

Takeaways

In Painters Partition problem, we haveM boards of length {l1, l2,… lM} to paint, and there are N painters available.

Example

Input 1: M = 5, N = 3, Arr = {5, 25, 30, 20, 15}

Output 1: 35

Input 2: M = 4, N = 2, Arr = {5, 6, 5, 6}

Output 2: 11

Input 3: M = 4, N = 2, Arr = {10, 15, 20, 25}

Output 3: 45

Example Explanation

Explanation for Input 1:
Allocation for Painter 1:{5,25}
Allocation for Painter 2: {30}
Allocation for Painter 3: {20,15}
When all of the painters have completed their work, the job will be completed, i.e., at time = $$ max (5+10, 30, 20+15) = 35 $$.

Explanation for Input 2:
Here, we’ll divide our array into two parts and assign the first two values to the first
painter, i.e., 11, and the last two values, i.e., 11, to the second painter.

Explanation for Input 3:
Similarly, here also, we’ll divide our array into two parts and assign the first two
values to the first painter, i.e., 25, and the last two values, i.e., 45, to the
second painter. So the answer would be 45.

Constraints

1 <= T <= 4
1 <= M <= 10^4
1 <= N <= M
1 <= Arr [i] <= 10^5

Where ‘T’ is the number of test cases,
“M” is the length of the given array (boards).
“N” is the number of painters available.
Arr[i] denotes the i-th element in the array.

Approach 1: Brute-Force Solution

The brute force approach could be that we consider all possible sets of contiguous partitions and we will calculate the maximum sum partition in each case and return the minimum of all these cases. Let’s see properly how it could be done.

Algorithm:

We can assume that we already have (N-1) partitions using (N-2) dividers. Now we have to make the (N-1)th divider to get N partitions. So simply, we can put in the (N-1)th divider to getN partitions. We will put the (N-1)th divider between the ith and (i+1)th elements, where i = 1 to n.

Note: Putting the (N-1)th divider before the first element or after the last element has the same effect.

We can calculate the total cost for the above arrangement as the maximum of the following:

• The final partition’s cost would be sum(Ai..An), where the (N-1)th divider comes before element i.
• The maximum cost of any partition formed to the left of the (N-1)th divider.

See the below recurrence relation:

Coding Implementation:

C++

#include <climits>
#include <iostream>
using namespace std;

// Calculate the sum between two indices in an array.
int add(int arr[], int strt, int end)
{
    int total = 0;
    for (int i = strt; i <= end; i++)
        total += arr[i];
    return total;
}

// Passing array of boards, the number of boards, and the number of painters
int partition(int arr[], int M, int N)
{
    // Base Cases
    if (M == 1)
        return arr[0];
    if (N == 1)
        return add(arr, 0, M - 1);

    int ans = INT_MAX;

    // Find the smallest of all possible maximum (N-1) partitions
    // to the left of arr[i], with i elements, and insert the
    // (N-1)th divider between arr[i-1] and arr[i].
    for (int i = 1; i <= M; i++)
        ans = min(ans, max(partition(arr, i, N - 1),
                           add(arr, i, M - 1)));

    return ans;
}

int main()
{
    int arr[] = {20, 50, 10, 30, 40, 80};
    int M = sizeof(arr) / sizeof(arr[0]);
    int N = 3;
    cout << partition(arr, M, N) << endl;
    return 0;
}

Output:

80

Java

import java.util.*;
import java.io.*;

class Scaler {
    // Calculate the sum between two indices in an array.
    static int add(int arr[], int from, int end) {
        int total = 0;
        for (int i = from; i <= end; i++)
            total += arr[i];
        return total;
    }

    // Passing array of boards, the number of boards, and the number of painters
    static int partition(int arr[], int M, int N) {
        // Base Cased
        if (M == 1)
            return arr[0];
        if (N == 1)
            return add(arr, 0, M - 1);

        int ans = Integer.MAX_VALUE;

        // Find the smallest of all possible maximum (N-1) partitions
        // to the left of arr[i], with i elements, and insert the
        // (N-1)th divider between arr[i-1] and arr[i].
        for (int i = 1; i <= M; i++)
            ans = Math.min(ans, Math.max(partition(arr, i, M - 1),
                    add(arr, i, M - 1)));

        return ans;
    }

    public static void main(String args[]) {
        int arr[] = { 20, 50, 10, 30, 40, 80 };
        int M = arr.length;
        int N = 3;
        res = partition(arr, M, N);
        System.out.println(res);
    }
}

Output:

80

Python

# Calculate the Sum between two indices in an array.
def add(arr, strt, end):
    total = 0
    for i in range(strt, end + 1):
        total += arr[i]
    return total

# Passing array of boards, the number of boards, and the number of painters
def partition(arr, M, N):
    # Base Case
    if M == 1:
        return arr[0]
    if N == 1:
        return add(arr, 0, M - 1)
    ans = 100000000

    # Find the smallest of all possible maximum (N-1) partitions
    # to the left of arr[i], with i elements, and insert the
    # (N-1)th divider between arr[i-1] and arr[i].
    for i in range(1, M + 1):
        ans = min(ans,
                  max(partition(arr, i, N - 1),
                      add(arr, i, M - 1)))
    return ans


arr = [20, 50, 10, 30, 40, 80]
M = len(arr)
N = 3
res = partition(arr, M, N)
print(res)

Output:

80

Python

# Calculate the Sum between two indices in an array.
def add(arr, strt, end):
    total = 0
    for i in range(strt, end + 1):
        total += arr[i]
    return total

# Passing array of boards, the number of boards, and the number of painters
def partition(arr, M, N):
    # Base Case
    if M == 1:
        return arr[0]
    if N == 1:
        return add(arr, 0, M - 1)
    ans = 100000000

    # Find the smallest of all possible maximum (N-1) partitions
    # to the left of arr[i], with i elements, and insert the
    # (N-1)th divider between arr[i-1] and arr[i].
    for i in range(1, M + 1):
        ans = min(ans,
                  max(partition(arr, i, N - 1),
                      add(arr, i, M - 1)))
    return ans


arr = [20, 50, 10, 30, 40, 80]
M = len(arr)
N = 3
res = partition(arr, M, N)
print(res)

Output:

80

Time Complexity

Time complexity would be exponential for the above algorithm.
$MMM*M$ ……… $N$ times = $O(M^N)$
where,
'N' is the number of painters.
'M' is the length of the given array (boards).

Space Complexity

Each function call of a recursive algorithm will take $O(N)$ space, and if the maximum depth of the recursion tree is 'M' then the recursive algorithm’s space complexity will be $O(NM)$.

Approach 2: Using Binary Search

In the previous algorithm, we discussed how we could solve this problem recursively by breaking it into subproblems, but that algorithm was taking more time and space. Now we will discuss a more efficient approach using binary search.

Algorithm

Here, our target value (that would always be in the searching range) is the maximum sum of a contiguous section in the allocation of boards. The highest value would always be the sum of all the elements in the array, and this will happen only when we allot 1 painter to all the sections of the board, and the lowest value could be the maximum value of the array.

Let’s see how it works:

1. We can allocate the maximum to one painter and divide the remaining sections so that their costs are minimized.
2. One interesting thing is that if we have p painters, the values in the range increase, and the value of p decreases, and vice-versa.
3. From this, we can find the target value when p=N.
4. Now, we can easily find the target values when p=N and use our helper functions to find p and the minimum number of painters required when there is a maximum length of section a painter can paint.

Code Implementation

C++

#include <iostream>
#include <climits>
using namespace std;

// Find maximum element of an array
int maxEle(int arr[], int M)
{
    int max = INT_MIN;
    for (int i = 0; i < M; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

// Find the sum of the elements in the array
int addArr(int arr[], int M)
{
    int res = 0;
    for (int i = 0; i < M; i++)
        res += arr[i];
    return res;
}

// Find minimum painters required for given maximum length (Length that painter can paint)
int paintersNumber(int arr[], int M, int maxLen)
{
    int res = 0, numPainters = 1;

    for (int i = 0; i < M; i++) {
        res += arr[i];

        if (res > maxLen) {
            res = arr[i];
            numPainters++;
        }
    }

    return numPainters;
}


int partition(int arr[], int M, int N)
{
    int strt = maxEle(arr, M);
    int end = addArr(arr, M);

    while (strt < end) {
        int mid = strt + (end - strt) / 2;
        int reqPainters = paintersNumber(arr, M, mid);
        // The current mid is enough to paint the paintboards by N painters. 
        // We move the right pointer to mid (The right half of the search space is eliminated).
        if (reqPainters <= N)
            end = mid;
        // Move the left point to mid+1 (The left half of the search space is omitted).
        // Here, mid is excluded because it gives required painters > N, which is invalid.
        else
            strt = mid + 1;
    }
    return strt;
}

int main()
{
    int arr[] = {20, 50, 10, 30, 40, 80};
    int M = sizeof(arr) / sizeof(arr[0]);
    int N = 3;
    cout << partition(arr, M, N) << endl;
    return 0;
}

Output:

80

Java

import java.util.*;
import java.io.*;

class Scaler {

    // Find maximum element of an array
    static int maxEle(int arr[], int M) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < M; i++)
            if (arr[i] > max)
                max = arr[i];
        return max;
    }

    // Find the sum of the elements in the array
    static int addArr(int arr[], int M) {
        int res = 0;
        for (int i = 0; i < M; i++)
            res += arr[i];
        return res;
    }

    // Find minimum painters required for given maximum length (Length that painter
    // can paint)
    static int paintersNumber(int arr[], int M, int maxLen) {
        int res = 0, numPainters = 1;

        for (int i = 0; i < M; i++) {
            res += arr[i];

            if (res > maxLen) {
                res = arr[i];
                numPainters++;
            }
        }

        return numPainters;
    }

    static int partition(int arr[], int M, int N) {
        int strt = maxEle(arr, M);
        int end = addArr(arr, M);

        while (strt < end) {
            int mid = strt + (end - strt) / 2;
            int requiredPainters = paintersNumber(arr, M, mid);
            
            // The current mid is enough to paint the paintboards by N painters. 
            // We move the right pointer to mid (The right half of the search space is eliminated).
            if (requiredPainters <= N)
                end = mid;
            // Move the left point to mid+1 (The left half of the search space is omitted).
            // Here, mid is excluded because it gives required painters > N, which is invalid.
            else
                strt = mid + 1;
        }
        return strt;
    }

    public static void main(String args[]) {
        int arr[] = { 20, 50, 10, 30, 40, 80 };
        int M = arr.length;
        int N = 3;
        System.out.println(partition(arr, M, N));
    }
}

Output:

80

Python

# Find minimum painters required for given maximum length(Length that painter can paint)
def paintersNumbers(arr, maxLen):
    res = 0
    numPainters = 1

    for i in arr:
        res += i

        if (res > maxLen):
            res = i
            numPainters += 1

    return numPainters


def partition(arr, M, N):
    strt = max(arr)
    end = sum(arr)

    while (strt < end):
        mid = strt + (end - strt) // 2
        requiredPainters = paintersNumbers(arr, mid)
        # The current mid is enough to paint the paintboards by N painters. 
        # We move the right pointer to mid (The right half of the search space is eliminated).
        if (requiredPainters <= N):
            end = mid
        # Move the left point to mid+1 (The left half of the search space is omitted).
        # Here, mid is excluded because it gives required painters > N, which is invalid.
        else:
            strt = mid + 1
    return strt


arr = [20, 50, 10, 30, 40, 80]
M = len(arr)
N = 3
ans = int(partition(arr, M, N))
print(ans)

Output:

80

Time Complexity

$ O(MlogM)$, where M is the length of the input array.
Here we are traversing an array of size Mand the partition function is taking the time
$logM$, so the total complexity would be $O(MlogM)$.

Space Complexity

O(1), as no extra space is used.

Conclusion

Now let’s summarize our topic by what we have learned so far.

• Putting the (N-1)th divider before or after the first element has the same effect.
• The board cannot be painted partially by one painter and partially by another, which means they cannot share the board to paint.
• The brute force approach could be that we consider all possible sets of contiguous partitions and we will calculate the maximum sum partition in each case and return the minimum of all these cases.
• In binary search approach, our target value (that would always be in the searching range) is the maximum sum of a contiguous section in the allocation of boards.