Find minimum time to finish all jobs

Array Dynamic Programming Backtracking Bit Manipulation Bitmask

45.4% acceptance

Feb 25, 2026

1130

You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the ith job. There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the maximum working time of any worker is minimized. Return the minimum possible maximum working time of any assignment.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_time_required(jobs: Vec<i32>, k: i32) -> i32 {
    let n = jobs.len();
    let full = 1usize << n;
    let k = k as usize;

    // Precompute sum for each bitmask of jobs
    let mut sum = vec![0i32; full];
    for mask in 1..full {
      let lsb = mask & mask.wrapping_neg();
      let bit = lsb.trailing_zeros() as usize;
      sum[mask] = sum[mask ^ lsb] + jobs[bit];
    }

    // dp[j][mask] = min max-time when j workers collectively cover jobs in mask
    let inf = i32::MAX;
    let mut dp = vec![vec![inf; full]; k + 1];
    for j in 0..=k { dp[j][0] = 0; }

    for j in 1..=k {
      for mask in 1..full {
        // Enumerate all non-empty submasks
        let mut sub = mask;
        while sub > 0 {
          if dp[j - 1][mask ^ sub] != inf {
            let candidate = dp[j - 1][mask ^ sub].max(sum[sub]);
            dp[j][mask] = dp[j][mask].min(candidate);
          }
          sub = (sub - 1) & mask;
        }
      }
    }

    dp[k][full - 1]
  }
}