Painter's Partition Problem InterviewBit Solution

Problem: Painter's Partition Problem

Problem Description:

Given 2 integers A and B and an array of integers C of size N.

Element C[i] represents the length of the ith board.

You have to paint all N boards [C0, C1, C2, C3 … CN-1]. There are A painters available and each of them takes B units of time to paint 1 unit of the board.

Calculate and return minimum time required to paint all boards under the constraints that any painter will only paint contiguous sections of the board.

• 2 painters cannot share a board to paint. That is to say, the board cannot be painted partially by one painter, and partially by another.

• A painter will only paint contiguous boards. Which means a the configuration where painter 1 paints board 1 and 3 but not 2 is invalid.

Return the ans % 10000003.

Input Format

The first argument given is the integer A.
The second argument given is the integer B.
The third argument given is the integer array C.

Output Format

Return minimum time required to paint all boards under the constraints that any painter will only paint contiguous sections of board % 10000003. 

Constraints

1 <=A <= 1000 
1 <= B <= 10^6 
1 <= C.size() <= 10^5 
1 <= C[i] <= 10^6

For Example

Input 1:
    A = 2
    B = 5
    C = [1, 10]
Output 1:
    50
Explanation 1:
    Possibility 1:- same painter paints both blocks, time taken = 55units
    Possibility 2:- Painter 1 paints block 1, painter 2 paints block 2, time take = max(5, 50) = 50
    There are no other distinct ways to paint boards.
    ans = 50%10000003

Input 2:
    A = 10
    B = 1
    C = [1, 8, 11, 3]
Output 2:
    11

Approach

This problem is similar to the problem, Allocate Books. So for detailed explanation, you can check out that.

In this problem, you have to do binary search on range of possible answer. The minimum answer possible is let's say 0 and the maximum answer possible is the sum of the length of all the boards multiplied by the time taken. Since the time is constant we can ignore it for now and just focus on minimizing the maximum length of the board given to any painter, as we can multiply the time later, while returning the answer.

So we can do binary search on the range from 0 to the sum of the length of all the boards. And for each mid value, let's called it threshold value, we can check whether we can allocate boards to the painters, without exceeding the threshold value. If it is possible to allot boards to the painters, then we will shift to the right, otherwise to the left.

Time & Space Complexity

Time Complexity: O(logN), N being the sum of array length of all boards. 

Space Complexity: O(1), Ignoring the space taken by the given input array.

Solution: