Painters’ Partition Problem

Let’s help some painters to finish their job efficiently!

Photo by David Pisnoy on Unsplash

Problem:
Given a number of painters and some boards, we have to find the minimum time in which the painters can paint those boards.

Conditions:
1. One board can not be partially painted by more than one painter.
2. One painter can paint only contiguous boards.

Inputs
A : Number of painters
B : Time it takes for one painter to paint one unit of board
C : Array of length of boards

Output:
Minimum time required to paint all boards.

Before jumping onto the solution, let’s see some examples, then get some observations from those and then approach to solve the problem.

Examples:

Example 1
A = 2 | B = 5 | C = [1, 10]

Since we have two painters with us, and there are only two boards, these are the possibilities:
1. One painter paints both the boards i.e 11 units which will take time = 11*5 = 55
2. One painter paints the first board, taking 1*5 = 5 units of time. Second painter paints the second board, taking 10*5 = 50 units of time.
Minimum time it will take to paint all the boards = 50

Example 2
A = 10 | B = 1 | C =[1, 8, 11, 3]

Since we have 10 painters with us which is greater than the number of boards we have, we can allocate one painter to every board.
P1 painting C1, taking time = 1*1 = 1
P2 painting C2, taking time = 8*1 = 8
P3 painting C3, taking time = 11*1 = 11
P4 painting C4, taking time = 3*1 = 3
Minimum time it will take to paint all the boards = 11

Example 3
A = 1 | B = 5 | C = [2,7,9,1]

Since we have only one painter with us, all the boards needs to be painted by the same painter, leaving us with only one possibility.
Time taken by the painter = (2+7+9+1)*5 = 85

Observations:

1. If we have unlimited painters, then the minimum time for all painters to paint all the boards will be to paint the maximum length board.
2. If we have only one painter, then that person has to paint all the boards, so minimum time it will take will be the sum of the lengths of the boards, multiplied by the time it takes to paint one unit.

Approach:

Upper limit of the minimum time would be when one painter has to paint all the boards. Lower limit of the minimum time would be when there are unlimited painters available, and the minimum time would be restricted by the time taken to paint the maximum length board.

Since we have to find the minimum time it requires to paint all the boards, and we know the upper and lower limit of the minimum time, we can do a “Binary Search” over the board units to paint, based on the following monotonicity observations:

Given a number which represents the maximum number of units one painter can paint, and we find the number of painters required to paint all the boards with this condition:

1. If the number of painters are more than the available painters (A), this means that if I have to work with A number of painters, I have to increase this limit of max units one can paint.
2. If the number of painters are less than the available painters (A), this means that I can ask A painters to do the same with lesser limit of max units one can paint.
3. If the number of painters are equal to the available painters (A), then also I can ask if A painters can paint all boards with lesser limit on one painter, which will in-turn lead me to the less paint units given to one painter and reducing paint time.

Pseudo Code:

int paint(int A, int B, int[] C) {
    low = getMax(C); // lower limit of min time
    high = getSum(C); // upper limit of min time
    while (low < high) {
        mid = (low + high) / 2;
        // get number of painters with max paint limit as mid
        n = getPaintersWithLimit(C, mid);
        if (A < n) 
            low = mid + 1;
        else 
            high = mid;
    }
    return getTimeForUnits(low);
}

Solution:

Solution to Painters Partition Problem in Java

rajatgoyal715/Programmers-Handbook