Scale Engineer

Minimum Difficulty of a Job Schedule

Hard
#1241Time: O(n^2 * d). There are `n * d` states for our `solve(i, daysLeft)` function. For each state, we iterate from `i` to `n - daysLeft`, which can be up to `O(n)` iterations. Inside the loop, we do constant time work (as the recursive call's result will be memoized). Thus, the total time complexity is `O(n * d * n) = O(n^2 * d)`.Space: O(n * d), where `n` is the number of jobs and `d` is the number of days. This is for the memoization table `memo`. The recursion stack depth is at most `d`.1 company
Patterns
Dynamic Programming
Data structures
Array
Companies
Turvo

Prompt

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.

 

Example 1:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7

Example 2:

Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

Example 3:

Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This problem has optimal substructure and overlapping subproblems, making it a good candidate for dynamic programming. A straightforward way to approach DP is through top-down recursion with memoization.

We can define a recursive function solve(i, d) that calculates the minimum difficulty to schedule jobs from index i to the end of the array within d days. To find the solution for the original problem, we would call solve(0, d).

In the function solve(i, d), we try all possible ways to schedule the jobs for the current day. We can schedule jobs from i to j, where j is a valid split point. The difficulty for this day would be the maximum job difficulty in the range [i, j]. The remaining jobs from j+1 to the end must then be scheduled in d-1 days. We recursively call our function for this subproblem: solve(j+1, d-1). We take the minimum over all possible split points j.

To avoid recomputing the same subproblem (i, d) multiple times, we use a 2D array memo to store the results. Before computing solve(i, d), we check if the result is already in our memoization table.

Algorithm

  1. Base Case: If the number of jobs n is less than the number of days d, it's impossible to schedule. Return -1.
  2. Recursive Function: Define a function, say solve(i, daysLeft), which computes the minimum difficulty to schedule jobs from index i to n-1 in daysLeft days.
  3. Memoization: Use a 2D array, memo[i][daysLeft], to store the results of subproblems to avoid re-computation. Initialize it with a value like -1.
  4. Recursive Step:
    • For the current day, we can take jobs from i to j. The number of remaining jobs n - (j+1) must be at least daysLeft - 1.
    • The difficulty for the current day is max(jobDifficulty[i...j]).
    • The difficulty for the remaining days is solve(j+1, daysLeft - 1).
    • We iterate through all valid split points j (from i to n - daysLeft) and find the minimum total difficulty: min(max(jobDifficulty[i...j]) + solve(j+1, daysLeft - 1)).
  5. Base Case for Recursion: If daysLeft is 1, we must schedule all remaining jobs (i to n-1) on this day. The difficulty is max(jobDifficulty[i...n-1]).
  6. Return Value: The final answer is the result of solve(0, d). If the result is infinity (or a very large number used for initialization), it means no valid schedule was found, but our initial check n < d should handle this.

Walkthrough

class Solution {    private int n;    private int[] jobDifficulty;    private int d;    private int[][] memo;     public int minDifficulty(int[] jobDifficulty, int d) {        this.n = jobDifficulty.length;        if (n < d) {            return -1;        }        this.jobDifficulty = jobDifficulty;        this.d = d;        this.memo = new int[n][d + 1];        for (int i = 0; i < n; i++) {            Arrays.fill(memo[i], -1);        }        return solve(0, d);    }     private int solve(int i, int daysLeft) {        // If we have already computed this subproblem, return the stored result.        if (memo[i][daysLeft] != -1) {            return memo[i][daysLeft];        }         // Base case: If only one day is left, we must do all remaining jobs.        // The difficulty for this day is the max difficulty among the remaining jobs.        if (daysLeft == 1) {            int maxDifficulty = 0;            for (int k = i; k < n; k++) {                maxDifficulty = Math.max(maxDifficulty, jobDifficulty[k]);            }            return memo[i][daysLeft] = maxDifficulty;        }         int minTotalDifficulty = Integer.MAX_VALUE;        int maxDifficultyCurrentDay = 0;         // Iterate through all possible split points 'j'.        // We must leave at least 'daysLeft - 1' jobs for the remaining days.        for (int j = i; j <= n - daysLeft; j++) {            maxDifficultyCurrentDay = Math.max(maxDifficultyCurrentDay, jobDifficulty[j]);            int remainingDifficulty = solve(j + 1, daysLeft - 1);                        // If the subproblem is solvable            if (remainingDifficulty != Integer.MAX_VALUE) {                minTotalDifficulty = Math.min(minTotalDifficulty, maxDifficultyCurrentDay + remainingDifficulty);            }        }         return memo[i][daysLeft] = minTotalDifficulty;    }}

Complexity

Time

O(n^2 * d). There are `n * d` states for our `solve(i, daysLeft)` function. For each state, we iterate from `i` to `n - daysLeft`, which can be up to `O(n)` iterations. Inside the loop, we do constant time work (as the recursive call's result will be memoized). Thus, the total time complexity is `O(n * d * n) = O(n^2 * d)`.

Space

O(n * d), where `n` is the number of jobs and `d` is the number of days. This is for the memoization table `memo`. The recursion stack depth is at most `d`.

Trade-offs

Pros

  • Relatively intuitive to formulate from the problem's recursive nature.

  • Correctly solves the problem within the given constraints.

Cons

  • The time and space complexity are not optimal.

  • Can lead to a StackOverflowError for very deep recursion, although d is small here, so it's not a major concern.

Solutions

class Solution {public  int minDifficulty(int[] jobDifficulty, int d) {    final int inf = 1 << 30;    int n = jobDifficulty.length;    int[][] f = new int[n + 1][d + 1];    for (var g : f) {      Arrays.fill(g, inf);    }    f[0][0] = 0;    for (int i = 1; i <= n; ++i) {      for (int j = 1; j <= Math.min(d, i); ++j) {        int mx = 0;        for (int k = i; k > 0; --k) {          mx = Math.max(mx, jobDifficulty[k - 1]);          f[i][j] = Math.min(f[i][j], f[k - 1][j - 1] + mx);        }      }    }    return f[n][d] >= inf ? -1 : f[n][d];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem