Painters Partition Problem

Problem Statement

Given an array of n boards where each board has a certain length, and k painters, such that each painter takes 1 unit of time to paint 1 unit of board. Find the minimum time to paint all boards under the following constraints:

1. A painter can only paint contiguous boards
2. Each board must be painted by exactly one painter

Constraints:

• 1 ≤ k ≤ n ≤ 10^5
• 1 ≤ boards[i] ≤ 10^5

Example:

• Input: boards = [10, 20, 30, 40], k = 2
• Output: 60
• Explanation: Painter 1 paints [10, 20, 30] = 60, Painter 2 paints [40] = 40. Max time = 60.

Example 2:

• Input: boards = [10, 10, 10, 10], k = 2
• Output: 20
• Explanation: Each painter paints 2 boards = 20 time units.

Approach 1: Brute Force (Recursion)

Intuition

Try all possible ways to partition the array into k contiguous parts and find the partition that minimizes the maximum sum.

Algorithm

1. Use recursion to place k-1 partition points
2. Calculate maximum sum for each partition configuration
3. Track the minimum of all maximum sums

public class Solution {
    private int minTime = Integer.MAX_VALUE;
    
    private int getSum(int[] boards, int start, int end) {
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum += boards[i];
        }
        return sum;
    }
    
    private void solve(int[] boards, int idx, int k, int currentMax) {
        int n = boards.length;
        
        if (k == 1) {
            int sum = getSum(boards, idx, n - 1);
            minTime = Math.min(minTime, Math.max(currentMax, sum));
            return;
        }
        
        for (int i = idx; i <= n - k; i++) {
            int sum = getSum(boards, idx, i);
            solve(boards, i + 1, k - 1, Math.max(currentMax, sum));
        }
    }
    
    public int paintersPartition(int[] boards, int k) {
        if (k > boards.length) return -1;
        
        minTime = Integer.MAX_VALUE;
        solve(boards, 0, k, 0);
        return minTime;
    }
}

Complexity Analysis

• Time Complexity: O(n^k) - Trying all ways to place k-1 partitions
• Space Complexity: O(k) - Recursion stack depth

Approach 2: Binary Search on Answer (Optimal)

Intuition

If we can complete painting with maximum time T, we can also complete with any time > T. This monotonic property allows binary search on the answer.

Key Observations:

1. Minimum possible time = max(boards[i]) (each painter gets at least one board)
2. Maximum possible time = sum(boards) (one painter does everything)
3. For a given time limit, greedily check if k painters are enough
4. Binary search to find minimum valid time

Algorithm

1. Set low = max(boards), high = sum(boards)
2. Binary search on maximum time
3. For each mid, check if we can paint with k painters
4. If possible, try smaller time; else, increase time

import java.util.*;

public class PaintersPartition {
    private boolean canPaint(int[] boards, int k, long maxTime) {
        int painters = 1;
        long currentTime = 0;
        
        for (int board : boards) {
            if (board > maxTime) return false;
            
            if (currentTime + board > maxTime) {
                painters++;
                currentTime = board;
                
                if (painters > k) return false;
            } else {
                currentTime += board;
            }
        }
        
        return true;
    }
    
    public long minTime(int[] boards, int k) {
        int n = boards.length;
        if (k > n) return -1;
        
        long low = 0, high = 0;
        for (int board : boards) {
            low = Math.max(low, board);
            high += board;
        }
        
        long result = high;
        
        while (low <= high) {
            long mid = low + (high - low) / 2;
            
            if (canPaint(boards, k, mid)) {
                result = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        PaintersPartition pp = new PaintersPartition();
        int[] boards = {10, 20, 30, 40};
        System.out.println(pp.minTime(boards, 2));  // Output: 60
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log(sum))
  • Binary search: O(log(sum - max)) iterations
  • Each canPaint: O(n)
• Space Complexity: O(1)

Variant: Return the Actual Partition

Similar Problems

| Problem | Description | |---------|-------------| | Book Allocation | Same as painters partition | | Split Array Largest Sum | Minimize maximum sum of k subarrays | | Capacity to Ship | Minimize ship capacity to deliver in D days | | Aggressive Cows | Maximize minimum distance |

Key Takeaways

1. Binary Search on Answer: When minimizing maximum (or maximizing minimum), binary search on the answer space
2. Monotonic Property: If time T works, all times > T also work
3. Greedy Verification: Greedily assign boards to painters and count required painters
4. Search Space Bounds: low = max(boards), high = sum(boards)
5. Contiguous Constraint: Painters must paint contiguous boards
6. Time = Units: Each unit of board takes 1 unit of time
7. Pattern Recognition: "Minimize maximum" → Binary Search on Answer