Painter's Partition Problem

Given an array where each element represents the length of a board, and an integer k representing the number of painters available, your task is to allocate the boards among the painters such that:

• Each painter paints only continuous sections of boards.
• All painters work simultaneously.
• The goal is to minimize the maximum time taken by any painter.

Assume that each unit length takes 1 unit of time to paint. Return the minimum possible time to paint all boards under these constraints.

If the input array is empty or k is zero, return 0.

Understanding the Problem

The Painter’s Partition Problem involves painting a sequence of boards, each with a certain length. The challenge is to assign these boards to a given number of painters such that each painter paints a contiguous segment of boards, and the time taken by the painter who paints the most is minimized.

For example, given board lengths [10, 20, 30, 40] and 2 painters, the goal is to split the work so that both painters are efficiently utilized, and the maximum workload assigned to any painter is as small as possible. A simple split like [10, 20] | [30, 40] leads to one painter painting boards totaling 30 and the other painting 70. But [10, 20, 30] | [40] results in 60 and 40, which is better. Our goal is to find such an optimal partition.

Step-by-Step Solution with Example

step 1: Understand constraints and rules

Each painter must paint a **contiguous** section of the board. No painter can skip or pick randomly. All painters work in parallel, and the **goal is to minimize the maximum workload** assigned to any single painter.

step 2: Identify search space using Binary Search

The minimum time any painter must spend is the **max length** of a single board (since no board can be split). The maximum time is the **sum** of all boards (if one painter paints everything). So we search between max(boards) and sum(boards).

step 3: Use Binary Search to find optimal time

We perform binary search in this range. For each mid-point (which is a candidate for maximum allowed workload), we check whether it's **possible to divide the boards** among the painters such that no one exceeds this limit.

step 4: Implement a helper function

This function simulates the partition. We go through each board and assign it to a painter. If adding a board would exceed the max allowed time, we assign it to the next painter. If we need more painters than allowed, the current mid value is too low and must be increased.

step 5: Work with the example [10, 20, 30, 40] and 2 painters

• Search range: 40 (max board) to 100 (sum).
• Mid = 70. Can we paint within 70 units? Try splitting: [10, 20, 30] = 60, [40] = 40 → valid.
• Try lower: Mid = 55. First group: [10, 20] = 30, next: [30] = 30, next: [40] = 40 → needs 3 painters → too many.
• Repeat until you find the **smallest maximum workload** that works, which is 60 in this case.

Edge Cases

• Empty board list: Nothing to paint. Return 0.
• Zero painters: No one to do the job. Return 0.
• One painter: Must paint everything. Return sum(boards).
• Boards = Painters: Each painter paints one board. Return max(boards).
• More painters than boards: Same as above; extra painters are unused. Return max(boards).

Finally

This is a classic **load balancing** problem, and binary search is a powerful tool to find the optimal solution efficiently. Instead of brute-force checking every possible split (which is too slow), we search over the answer space intelligently using a helper function that simulates the partitioning process.

Time complexity is O(N log S), where N is the number of boards and S is the range of total paint time. This makes it scalable even for large inputs.

1. Set low = max(board), high = sum(board).
2. While low ≤ high:
   1. Calculate mid = (low + high) / 2.
   2. Check if it's possible to paint all boards within this time limit using ≤ K painters.
   3. If possible, store the result and move high = mid - 1.
   4. If not, move low = mid + 1.
3. Return the result found as the minimum time.

#include <stdio.h>

int isPossible(int boards[], int n, int k, int maxTime) {
    int painters = 1, currTime = 0;
    for (int i = 0; i < n; i++) {
        if (boards[i] > maxTime) return 0;
        if (currTime + boards[i] > maxTime) {
            painters++;
            currTime = boards[i];
        } else {
            currTime += boards[i];
        }
    }
    return painters <= k;
}

int paintersPartition(int boards[], int n, int k) {
    int low = boards[0], high = 0, result = 0;
    for (int i = 0; i < n; i++) {
        if (boards[i] > low) low = boards[i];
        high += boards[i];
    }
    result = high;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (isPossible(boards, n, k, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    int boards[] = {10, 20, 30, 40};
    int n = 4, k = 2;
    printf("Minimum time to paint all boards: %d\n", paintersPartition(boards, n, k));
    return 0;
}

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

bool isPossible(int boards[], int n, int k, int maxTime) {
    int painters = 1, currTime = 0;
    for (int i = 0; i < n; i++) {
        if (boards[i] > maxTime) return false;
        if (currTime + boards[i] > maxTime) {
            painters++;
            currTime = boards[i];
        } else {
            currTime += boards[i];
        }
    }
    return painters <= k;
}

int paintersPartition(int boards[], int n, int k) {
    int low = *max_element(boards, boards + n);
    int high = 0;
    for (int i = 0; i < n; i++) high += boards[i];
    int result = high;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (isPossible(boards, n, k, mid)) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    int boards[] = {10, 20, 30, 40};
    int n = 4, k = 2;
    cout << "Minimum time to paint all boards: " << paintersPartition(boards, n, k) << endl;
    return 0;
}

def is_possible(boards, k, max_time):
    painters = 1
    curr_time = 0
    for length in boards:
        if length > max_time:
            return False
        if curr_time + length > max_time:
            painters += 1
            curr_time = length
        else:
            curr_time += length
    return painters <= k

def painters_partition(boards, k):
    low = max(boards)
    high = sum(boards)
    result = high

    while low <= high:
        mid = (low + high) // 2
        if is_possible(boards, k, mid):
            result = mid
            high = mid - 1
        else:
            low = mid + 1

    return result

boards = [10, 20, 30, 40]
k = 2
print("Minimum time to paint all boards:", painters_partition(boards, k))

public class PaintersPartition {
  static boolean isPossible(int[] boards, int k, int maxTime) {
    int painters = 1, currTime = 0;
    for (int length : boards) {
      if (length > maxTime) return false;
      if (currTime + length > maxTime) {
        painters++;
        currTime = length;
      } else {
        currTime += length;
      }
    }
    return painters <= k;
  }

  static int paintersPartition(int[] boards, int k) {
    int low = 0, high = 0;
    for (int b : boards) {
      low = Math.max(low, b);
      high += b;
    }
    int result = high;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (isPossible(boards, k, mid)) {
        result = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return result;
  }

  public static void main(String[] args) {
    int[] boards = {10, 20, 30, 40};
    int k = 2;
    System.out.println("Minimum time to paint all boards: " + paintersPartition(boards, k));
  }
}

function isPossible(boards, k, maxTime) {
  let painters = 1, currTime = 0;
  for (let length of boards) {
    if (length > maxTime) return false;
    if (currTime + length > maxTime) {
      painters++;
      currTime = length;
    } else {
      currTime += length;
    }
  }
  return painters <= k;
}

function paintersPartition(boards, k) {
  let low = Math.max(...boards);
  let high = boards.reduce((a, b) => a + b, 0);
  let result = high;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (isPossible(boards, k, mid)) {
      result = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return result;
}

const boards = [10, 20, 30, 40];
const k = 2;
console.log("Minimum time to paint all boards:", paintersPartition(boards, k));

package main

import (
    "fmt"
)

func isPossible(boards []int, k int, maxTime int) bool {
    painters := 1
    currTime := 0
    for _, length := range boards {
        if length > maxTime {
            return false
        }
        if currTime + length > maxTime {
            painters++
            currTime = length
        } else {
            currTime += length
        }
    }
    return painters <= k
}

func paintersPartition(boards []int, k int) int {
    low, high := boards[0], 0
    for _, b := range boards {
        if b > low {
            low = b
        }
        high += b
    }
    result := high
    for low <= high {
        mid := (low + high) / 2
        if isPossible(boards, k, mid) {
            result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return result
}

func main() {
    boards := []int{10, 20, 30, 40}
    k := 2
    fmt.Println("Minimum time to paint all boards:", paintersPartition(boards, k))
}

fn is_possible(boards: &Vec<i32>, k: i32, max_time: i32) -> bool {
    let mut painters = 1;
    let mut curr_time = 0;
    for &length in boards.iter() {
        if length > max_time {
            return false;
        }
        if curr_time + length > max_time {
            painters += 1;
            curr_time = length;
        } else {
            curr_time += length;
        }
    }
    painters <= k
}

fn painters_partition(boards: Vec<i32>, k: i32) -> i32 {
    let mut low = *boards.iter().max().unwrap();
    let mut high: i32 = boards.iter().sum();
    let mut result = high;
    while low <= high {
        let mid = (low + high) / 2;
        if is_possible(&boards, k, mid) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    result
}

fn main() {
    let boards = vec![10, 20, 30, 40];
    let k = 2;
    println!("Minimum time to paint all boards: {}", painters_partition(boards, k));
}

fun isPossible(boards: IntArray, k: Int, maxTime: Int): Boolean {
    var painters = 1
    var currTime = 0
    for (length in boards) {
        if (length > maxTime) return false
        if (currTime + length > maxTime) {
            painters++
            currTime = length
        } else {
            currTime += length
        }
    }
    return painters <= k
}

fun paintersPartition(boards: IntArray, k: Int): Int {
    var low = boards.maxOrNull() ?: 0
    var high = boards.sum()
    var result = high
    while (low <= high) {
        val mid = (low + high) / 2
        if (isPossible(boards, k, mid)) {
            result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return result
}

fun main() {
    val boards = intArrayOf(10, 20, 30, 40)
    val k = 2
    println("Minimum time to paint all boards: ${paintersPartition(boards, k)}")
}

func isPossible(_ boards: [Int], _ k: Int, _ maxTime: Int) -> Bool {
    var painters = 1
    var currTime = 0
    for length in boards {
        if length > maxTime {
            return false
        }
        if currTime + length > maxTime {
            painters += 1
            currTime = length
        } else {
            currTime += length
        }
    }
    return painters <= k
}

func paintersPartition(_ boards: [Int], _ k: Int) -> Int {
    var low = boards.max() ?? 0
    var high = boards.reduce(0, +)
    var result = high

    while low <= high {
        let mid = (low + high) / 2
        if isPossible(boards, k, mid) {
            result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return result
}

let boards = [10, 20, 30, 40]
let k = 2
print("Minimum time to paint all boards: \(paintersPartition(boards, k))")

function isPossible(boards: number[], k: number, maxTime: number): boolean {
  let painters = 1, currTime = 0;
  for (let length of boards) {
    if (length > maxTime) return false;
    if (currTime + length > maxTime) {
      painters++;
      currTime = length;
    } else {
      currTime += length;
    }
  }
  return painters <= k;
}

function paintersPartition(boards: number[], k: number): number {
  let low = Math.max(...boards);
  let high = boards.reduce((a, b) => a + b, 0);
  let result = high;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (isPossible(boards, k, mid)) {
      result = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return result;
}

const boards: number[] = [10, 20, 30, 40];
const k: number = 2;
console.log("Minimum time to paint all boards:", paintersPartition(boards, k));

Time complexity

Space complexity

O(1)

Only constant extra space is used for counters and limits, no additional data structures.