Minimum difficulty of a job schedule

Array Dynamic Programming

59.7% acceptance

Feb 25, 2026

3588

336

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the jobs j where 0 <= j < i). You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done on that day. You are given an integer array jobDifficulty and an integer d. The difficulty of the ith job is jobDifficulty[i]. Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_difficulty(job_difficulty: Vec<i32>, d: i32) -> i32 {
    let n = job_difficulty.len();
    let d = d as usize;
    if n < d { return -1; }
    const INF: i32 = i32::MAX / 2;
    // dp[i][j] = min difficulty using first j+1 jobs in i+1 days
    // i in [0..d), j in [0..n)
    let mut dp = vec![vec![INF; n]; d];
    // Base case: 1 day
    dp[0][0] = job_difficulty[0];
    for j in 1..n {
      dp[0][j] = dp[0][j - 1].max(job_difficulty[j]);
    }
    for day in 1..d {
      for j in day..n {
        let mut max_diff = 0;
        // k = last job index done in previous days; today we do jobs [k+1..=j]
        // As k decreases, we add job at k+1 to today's schedule
        for k in (day - 1..j).rev() {
          max_diff = max_diff.max(job_difficulty[k + 1]);
          if dp[day - 1][k] < INF {
            dp[day][j] = dp[day][j].min(dp[day - 1][k] + max_diff);
          }
        }
      }
    }
    if dp[d - 1][n - 1] == INF { -1 } else { dp[d - 1][n - 1] }
  }
}