Optimal Assembly Line

Tags

Optimal Assembly Line

Category

Searching

Difficulty

Hard

Problem Statement

Given an array of positive integers representing task durations and a number k representing the number of workers (or assembly line stations), assign all tasks to the k workers such that the maximum total duration assigned to any single worker is minimized. Tasks must be assigned contiguously (i.e., each worker gets a consecutive block of tasks). Return the minimized maximum load.

Intuition

This is a classic binary search on the answer problem. The minimum possible maximum load is the largest single task (when a worker gets just that one task), and the maximum possible load is the sum of all tasks (when one worker does everything). We binary search on the answer: for a given candidate maximum load, we greedily check whether it is possible to partition the tasks into at most k contiguous groups, each with a total duration not exceeding the candidate.

Approach

  1. Set low = max(tasks) and high = sum(tasks).
  2. Binary search while low < high: a. mid = (low + high) / 2. b. Check if we can assign all tasks to k workers with no worker exceeding mid:
    • Greedily assign tasks left-to-right. Start a new worker whenever adding the next task would exceed mid.
    • Count the workers needed. c. If workers needed <= k, set high = mid (we might do better). d. Otherwise, set low = mid + 1 (mid is too small).
  3. Return low.

Pseudocode

function optimalAssemblyLine(tasks, k):
    low = max(tasks)
    high = sum(tasks)

    while low < high:
        mid = (low + high) / 2
        if canAssign(tasks, k, mid):
            high = mid
        else:
            low = mid + 1

    return low

function canAssign(tasks, k, maxLoad):
    workers = 1
    currentLoad = 0

    for task in tasks:
        if currentLoad + task > maxLoad:
            workers++
            currentLoad = task
            if workers > k:
                return false
        else:
            currentLoad += task

    return true

Time & Space Complexity

  • Time: O(n * log(S)) where n is the number of tasks and S is the sum of all task durations. The binary search runs O(log(S)) iterations, each requiring an O(n) feasibility check.
  • Space: O(1) — Only a constant number of variables.

Key Insights

  • "Binary search on the answer" is a powerful paradigm: when you cannot directly compute the optimal answer but can efficiently verify whether a candidate answer is feasible, binary search bridges the gap.
  • The greedy feasibility check works because tasks must be contiguous. Assigning as many tasks as possible to the current worker before starting a new one is provably optimal for minimizing the number of workers.
  • The lower bound max(tasks) is critical: no matter how many workers we have, at least one must handle the largest task.

Edge Cases

  • One worker (k = 1): the answer is the sum of all tasks.
  • Workers equal to tasks (k = n): the answer is the maximum single task.
  • More workers than tasks (k > n): same as k = n.
  • All tasks have equal duration: the answer is ceil(n / k) * taskDuration.
  • A single very large task dominating: the answer is that task's duration.

Linked mentions