Minimum Difficulty of a Job Schedule

Hard
898.

Minimum Difficulty of a Job Schedule

Minimum Difficulty of a Job Schedule is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and Atlassian interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} jobDifficulty
 * @param {number} d
 * @return {number}
 */
var minDifficulty = function(jobDifficulty, d) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Difficulty of a Job Schedule — Problem & Solution

Minimum Difficulty of a Job Schedule solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Difficulty of a Job Schedule is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and Atlassian interviews.

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

Hints for Minimum Difficulty of a Job Schedule

  1. Hint 1

    Jobs stay in order, so a schedule is just a way to cut the array into d contiguous blocks.

  2. Hint 2

    dp[day][i] is the best difficulty for the first i jobs using day days.

  3. Hint 3

    Extend backwards from i, tracking the running maximum of the last block as it grows.

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]

Java

public static int minDifficulty(int[] jobDifficulty, int d) {
    final int INF = 1000000000;
    int n = jobDifficulty.length;
    if (n < d) return -1;
    int[] prev = new int[n + 1];
    Arrays.fill(prev, INF);
    prev[0] = 0;
    for (int day = 1; day <= d; day++) {
        int[] cur = new int[n + 1];
        Arrays.fill(cur, INF);
        for (int i = day; i <= n; i++) {
            int mx = 0;
            for (int j = i; j >= day; j--) {
                mx = Math.max(mx, jobDifficulty[j - 1]);
                if (prev[j - 1] < INF) cur[i] = Math.min(cur[i], prev[j - 1] + mx);
            }
        }
        prev = cur;
    }
    return prev[n];
}

C++

int minDifficulty(vector<int>& jobDifficulty, int d) {
    const int INF = 1000000000;
    int n = (int) jobDifficulty.size();
    if (n < d) return -1;
    vector<int> prev(n + 1, INF);
    prev[0] = 0;
    for (int day = 1; day <= d; day++) {
        vector<int> cur(n + 1, INF);
        for (int i = day; i <= n; i++) {
            int mx = 0;
            for (int j = i; j >= day; j--) {
                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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming