Get started

Minimum Difficulty of a Job Schedule — Hard Problem & Solution

Jobs must be done in order over exactly d days, with at least one job each day.

  • Difficulty: Hard
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Jobs must be done in order over exactly d days, with at least one job each day. A day's difficulty is the maximum difficulty among the jobs done that day, and the schedule's difficulty is the sum over the days.

Return the minimum possible schedule difficulty, or -1 if there are fewer jobs than days.

Example 1

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: Day 1 takes the first five jobs (difficulty 6), day 2 takes the last (difficulty 1).

Example 2

Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: Not enough jobs to fill four days.

Example 3

Input: jobDifficulty = [1,1,1], d = 3
Output: 3

Constraints

  • 1 <= jobDifficulty.length <= 300
  • 0 <= jobDifficulty[i] <= 1000
  • 1 <= d <= 10

How to solve Minimum Difficulty of a Job Schedule

A partition DP. The only choice is where each day's block starts, and sweeping that start backwards lets the block's maximum be maintained incrementally instead of recomputed.

Approach

  1. Return -1 immediately when there are fewer jobs than days.
  2. dp[day][i] is the minimum difficulty of scheduling the first i jobs in day days; dp[0][0] = 0.
  3. For each i, walk j from i down to day, growing the running maximum of jobDifficulty[j-1 … i-1], and take dp[day-1][j-1] + max.
  4. The answer is dp[d][n].

Why it works

Because jobs cannot be reordered, every schedule is a partition into d contiguous non-empty blocks — so enumerating the last block's start covers all of them. Sweeping j downwards means each new j only extends the block leftwards by one job, so the maximum updates in constant time and the inner loop stays linear.

Complexity

  • Time — O(d · n²)
  • Space — O(n)

Pitfalls

  • Each day needs at least one job, which is what the j >= day bound enforces.
  • Recomputing the block maximum from scratch makes the inner loop quadratic and the whole thing O(d · n³).
  • A greedy split by equal totals is wrong — the objective is a sum of maxima, not of sums.

Reference solution

Python

from typing import List

def minDifficulty(jobDifficulty: List[int], d: int) -> int:
    n = len(jobDifficulty)
    if n < d:
        return -1
    INF = 10 ** 9
    prev = [INF] * (n + 1)
    prev[0] = 0
    for day in range(1, d + 1):
        cur = [INF] * (n + 1)
        for i in range(day, n + 1):
            mx = 0
            for j in range(i, day - 1, -1):
                mx = max(mx, jobDifficulty[j - 1])
                if prev[j - 1] < INF:
                    cur[i] = min(cur[i], prev[j - 1] + mx)
        prev = cur
    return prev[n]

JavaScript

var minDifficulty = function(jobDifficulty, d) {
    var INF = 1000000000;
    var n = jobDifficulty.length;
    if (n < d) return -1;
    var prev = [], t;
    for (t = 0; t <= n; t++) prev.push(INF);
    prev[0] = 0;
    for (var day = 1; day <= d; day++) {
        var cur = [];
        for (t = 0; t <= n; t++) cur.push(INF);
        for (var i = day; i <= n; i++) {
            var mx = 0;
            for (var j = i; j >= day; j--) {
                if (jobDifficulty[j - 1] > mx) mx = jobDifficulty[j - 1];
                if (prev[j - 1] < INF && prev[j - 1] + mx < cur[i]) cur[i] = prev[j - 1] + mx;
            }
        }
        prev = cur;
    }
    return prev[n];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue