Watch 10 video solutions for Minimum Difficulty of a Job Schedule, a hard level problem involving Array, Dynamic Programming. This walkthrough by codestorywithMIK has 89,157 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 3000 <= jobDifficulty[i] <= 10001 <= d <= 10Problem Overview: You receive an array jobDifficulty where each value represents the difficulty of a job, and an integer d representing the number of days. Jobs must be done in order, and at least one job must be scheduled each day. The difficulty of a day equals the maximum difficulty among jobs done that day. The goal is to split the array into d contiguous groups so the sum of daily difficulties is minimized.
Approach 1: Recursive Approach with Memoization (Time: O(n^2 * d), Space: O(n * d))
This approach models the problem as a decision at each job index: where should the current day's schedule end? For a starting index i and remaining days k, iterate forward and assign jobs i..j to the current day. Track the running maximum difficulty for that segment. The remaining jobs j+1..n-1 must then be scheduled in k-1 days. Use recursion to explore these splits and store results in a memo table keyed by (index, daysRemaining). Memoization avoids recomputing overlapping states. This turns an exponential recursion into polynomial time. The nested iteration over possible cut points results in O(n^2 * d) time.
Approach 2: Dynamic Programming with Bottom-Up Approach (Time: O(n^2 * d), Space: O(n * d))
The bottom-up dynamic programming version builds the same state iteratively. Define dp[i][k] as the minimum difficulty to schedule the first i jobs across k days. For each state, try all possible last-day partitions: iterate backward from job i and track the maximum difficulty of the segment assigned to the final day. Combine this value with dp[j-1][k-1], which represents scheduling the earlier jobs in fewer days. Update the minimum across all valid splits. The iteration order ensures smaller subproblems are already computed. This DP formulation avoids recursion overhead and is typically preferred in production code.
The key insight across both approaches is that the difficulty of a day depends only on the maximum job difficulty in its segment. By iterating possible segment boundaries and maintaining a running maximum, you efficiently evaluate every valid partition while reusing results for overlapping subproblems. This structure makes the problem a classic application of dynamic programming over a linear array.
Recommended for interviews: Interviewers expect the dynamic programming formulation. Start by describing the recursive partition idea because it clearly explains the state and transition. Then convert it into bottom-up DP for an optimal O(n^2 * d) solution with O(n * d) space. Showing both demonstrates understanding of recursion, memoization, and iterative DP design.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n^2 * d) | O(n * d) | Good for understanding the partition decision process and explaining the recurrence during interviews. |
| Bottom-Up Dynamic Programming | O(n^2 * d) | O(n * d) | Preferred implementation for coding interviews and production because it avoids recursion overhead. |