AlgoMaster Logo

Minimum Difficulty of a Job Schedule

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We have n jobs that must be done in order (job 0 before job 1 before job 2, etc.), and we need to split them across exactly d days. Each day must have at least one job. The cost of a day is the maximum difficulty among all jobs assigned to that day, and we want to minimize the total cost across all days.

This is essentially a partition problem: split the array jobDifficulty into exactly d contiguous segments, where each segment has at least one element, and minimize the sum of the maximum value in each segment.

This has optimal substructure. The best way to schedule the first i jobs in k days can be built from the best way to schedule a prefix in k-1 days, trying every possible split point for the last day. That structure points to dynamic programming.

Key Constraints:

  • 1 <= jobDifficulty.length <= 300. With n at most 300, an O(n^2 d) solution runs in roughly 300 300 * 10 = 900,000 operations, which is fast enough.
  • 1 <= d <= 10. Because d is bounded by 10, it works well as one of the DP dimensions.
  • 0 <= jobDifficulty[i] <= 1000. The largest possible total is 300 * 1000 = 300,000, so the sum fits in a 32-bit integer with no overflow risk.

Approach 1: Top-Down DP (Recursion with Memoization)

Intuition

On day 1, we decide how many jobs to do. We must do at least one, and we must leave enough jobs so that each remaining day still gets at least one. After fixing the jobs for today, the rest of the problem is the same kind of question over fewer jobs and fewer days, which we solve recursively.

Let solve(i, k) be the minimum difficulty to schedule jobs from index i onward using exactly k days. For the current day, we try assigning jobs i, i+1, ..., up to some endpoint j. The cost of this day is max(jobDifficulty[i..j]), and then we recursively solve solve(j+1, k-1) for the remaining jobs and days.

The base case: if k == 1, we must do all remaining jobs in one day, so the cost is max(jobDifficulty[i..n-1]).

Algorithm

  1. If n < d, return -1 (not enough jobs for each day to have at least one).
  2. Define a recursive function solve(i, k) meaning: minimum cost to schedule jobs from index i through n-1 in exactly k days.
  3. Base case: if k == 1, return the maximum of jobDifficulty[i..n-1].
  4. For the current day, try ending at every valid index j from i to n-k. Track the running maximum as we extend j.
  5. For each choice, the cost is currentMax + solve(j+1, k-1). Take the minimum over all choices.
  6. Memoize results to avoid recomputation.

Example Walkthrough

1solve(0, 2): Try day 1 ending at j=0..4, track running max
0
start
6
1
5
2
4
3
3
4
2
5
1
1/6

Code

The same computation can be expressed bottom-up, filling the table iteratively instead of through recursion. The bottom-up form makes the inner loop easier to reason about and sets up the stack-based optimization that follows.

Approach 2: Bottom-Up DP

Intuition

Instead of thinking top-down, we build the solution iteratively. Let dp[i][k] represent the minimum difficulty to schedule the first i jobs in exactly k days.

The transition: for the k-th day, we assign some contiguous block of jobs ending at job i. If the k-th day covers jobs from index j to i-1, then dp[i][k] = min over j of (dp[j][k-1] + max(jobDifficulty[j..i-1])).

We iterate j backward from i-1 down to k-1, tracking the running maximum. This avoids recomputing the maximum from scratch for each j.

Algorithm

  1. If n < d, return -1.
  2. Create a 2D array dp of size (n+1) x (d+1), initialized to infinity. Set dp[0][0] = 0.
  3. For each day k from 1 to d:
    • For each total job count i from k to n:
      • Iterate j backward from i down to k. Track the running maximum of jobDifficulty[j-1..i-1].
      • Update dp[i][k] = min(dp[i][k], dp[j-1][k-1] + runningMax).
  4. Return dp[n][d].

Example Walkthrough

1Day 1 complete: dp[i][1] = max(jobs[0..i-1]) = 6 for all i. Now compute Day 2.
0
0
base
1
6
6
2
6
6
3
6
6
4
6
6
5
6
6
6
6
6
1/6

Code

The inner loop rescans every split point from scratch for each position, which is where the second factor of n comes from. A monotonic stack removes that rescan by carrying the best split point forward as we move left to right, dropping the total to O(n * d).

Approach 3: DP with Monotonic Stack (Optimal)

Intuition

Fix a day k and compute dp[i][k] for all i from left to right. When job i is more difficult than some earlier job j (j < i), every last-day segment that previously had jobDifficulty[j] as its maximum now has jobDifficulty[i] as its maximum instead. Those earlier positions can be folded into the new one rather than recomputed.

A monotonic stack tracks this. The stack holds indices with strictly decreasing job difficulty. Before placing index i, pop every index whose difficulty is at most jobDifficulty[i], and for each popped index update dp[i] to reflect the larger maximum. After the pops, the stack top (if any) is an index more difficult than i, so its stored dp value already accounts for that larger maximum, and we take it directly.

Algorithm

  1. If n < d, return -1.
  2. Use a 1D dp array (space-optimized). Process day by day.
  3. For each day k from 1 to d, iterate through jobs left to right:
    • Maintain a monotonic stack of pairs (job index, minimum dp value achievable).
    • For job i, start with a candidate: dp[i] = prevDp[i-1] + jobDifficulty[i].
    • Pop stack entries whose job difficulty is less than or equal to jobDifficulty[i]. For each popped entry, update dp[i] by replacing the old max with the new max.
    • If the stack is not empty, check if the top has a better dp value.
    • Push the current entry onto the stack.
  4. Return dp[n-1] after processing all d days.

Example Walkthrough

1Day 1 done: prevDp = [6, 6, 6, 6, 6, 6]. Now compute Day 2 with monotonic stack.
0
INF
1
INF
2
INF
3
INF
4
INF
5
INF
1/6

Code