1335. Minimum Difficulty of a Job Schedule
Asked at Atlassian, Microsoft
Difficulty
Hard
Time
O(n^2 * d)
Space
O(n * d)
Pattern
Array
Companies
2
Problem
You are given an array jobDifficulty, where jobDifficulty[i] is the difficulty of the i-th job, and an integer d (the number of days). The jobs must be done in order: job i can only start after jobs 0..i-1 are finished. So a schedule is just a way to cut the array into d consecutive blocks, one block per day.
Every day must contain at least one job. The cost of a day is the maximum difficulty among the jobs done that day. The total cost of a schedule is the sum of the d daily costs. Return the minimum possible total cost.
If d is larger than the number of jobs, no valid schedule exists (some day would be empty), so return -1.
Cut the jobs into d ordered blocks
Constraints
- ●
1 <= jobDifficulty.length <= 300 - ●
0 <= jobDifficulty[i] <= 1000 - ●
1 <= d <= 10
Examples
jobDifficulty = [6,5,4,3,2,1], d = 27jobDifficulty = [9,9,9], d = 4-1jobDifficulty = [1,1,1], d = 33Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Atlassian | Hard | View all Atlassian questions → |
| Microsoft | Hard | View all Microsoft questions → |
How to Think About It
At each day, you decide how many jobs to complete. The remaining jobs go to subsequent days. The key insight: the difficulty of a day is the max job difficulty on that day. So adding harder jobs to a day increases its cost.
The recurrence: dp[i][j] = minimum difficulty to complete jobs from index i to the end in exactly j days. dp[i][j] = min over all splits k: max(jobs[i..k]) + dp[k+1][j-1].
Base case: dp[n][0] = 0 (no jobs, no days = cost 0). dp[i][1] = max of jobs[i..n-1] (all remaining jobs in one day).
Base case: if n < d, return -1 (not enough jobs for one per day). If n == d, sum all jobs (each day gets one job, difficulty = that job).
Optimal Approach
Step 1: If n < d, return -1.
Step 2: Create dp[i][j] = minimum difficulty to schedule jobs from i to end in j days.
Step 3: Fill from right to left, bottom to top:
- For j=1 (last day): dp[i][1] = max(jobs[i..n-1])
- For j>1: dp[i][j] = min over k from i to n-j: max(jobs[i..k]) + dp[k+1][j-1]
Step 4: Return dp[0][d].
The key observation: for each day, you try every possible split point. The difficulty of that day is the max difficulty in its range. Add the cost of the remaining days.
Time: O(n^2 * d) -- for each of d days, for each starting position, try all split points. Space: O(n * d).
DP over start index and days left
What Trips People Up in Real Interviews
Using a greedy approach. Greedy doesn't work here because the daily cost is the max, not the sum. Splitting hard jobs into separate days might not be optimal if it forces easy jobs into a day with a hard job.
Forgetting the base case dp[n][0] = 0. Without this, the recurrence can't compute costs for the last day properly.
Not checking if n < d. If there are fewer jobs than days, it's impossible to complete. Return -1 immediately.
Computing dp[i][j] in the wrong order. You need dp[k+1][j-1] (fewer days, later start) to be already computed. Fill from right to left for jobs and bottom to top for days.
Using O(n * d) memory without realizing you only need the previous day's values. You can optimize to O(n) space, but O(n * d) is acceptable.
Solution Code
O(n^2 * d) timedef minDifficulty(jobDifficulty, d):
n = len(jobDifficulty)
if n < d:
return -1
INF = float('inf')
dp = [[INF] * (d + 1) for _ in range(n + 1)]
dp[n][0] = 0
for i in range(n - 1, -1, -1):
dp[i][1] = max(jobDifficulty[i:])
for j in range(2, d + 1):
for i in range(n - j + 1):
maxd = 0
for k in range(i, n - j + 1):
maxd = max(maxd, jobDifficulty[k])
dp[i][j] = min(dp[i][j], maxd + dp[k + 1][j - 1])
return dp[0][d]Frequently Asked Questions
What is the Minimum Difficulty of a Job Schedule problem?
You have a list of jobs with daily difficulties. Schedule all jobs in exactly d days, completing at least one job per day. The difficulty of a day is the maximum difficulty of jobs done that day. Minimize the sum of daily difficulties. This is a 1D DP problem with a nested max operation.
How do you solve Minimum Difficulty of a Job Schedule?
The optimal approach runs in O(n^2 * d) time and O(n * d) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Minimum Difficulty of a Job Schedule?
Minimum Difficulty of a Job Schedule is asked at Atlassian, Microsoft. It is a hard difficulty problem.
What are common mistakes on Minimum Difficulty of a Job Schedule?
- Using a greedy approach. Greedy doesn't work here because the daily cost is the max, not the sum. Splitting hard jobs into separate days might not be optimal if it forces easy jobs into a day with a hard job.
- Forgetting the base case `dp[n][0] = 0`. Without this, the recurrence can't compute costs for the last day properly.
- Not checking if `n < d`. If there are fewer jobs than days, it's impossible to complete. Return -1 immediately.
- Computing `dp[i][j]` in the wrong order. You need `dp[k+1][j-1]` (fewer days, later start) to be already computed. Fill from right to left for jobs and bottom to top for days.
- Using `O(n * d)` memory without realizing you only need the previous day's values. You can optimize to `O(n)` space, but `O(n * d)` is acceptable.