Minimum Difficulty of a Job Schedule
Asked at Atlassian, Microsoft
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.
Asked At
| 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).
Visual walkthrough for jobDifficulty = [6,5,4,3,2,1], d = 2:
We need to split into 2 days. Try every split point:
- Day 1: [6], Day 2: [5,4,3,2,1] -> 6 + 5 = 11
- Day 1: [6,5], Day 2: [4,3,2,1] -> 6 + 4 = 10
- Day 1: [6,5,4], Day 2: [3,2,1] -> 6 + 3 = 9
- Day 1: [6,5,4,3], Day 2: [2,1] -> 6 + 2 = 8
- Day 1: [6,5,4,3,2], Day 2: [1] -> 6 + 1 = 7
Best: 7 (split after index 4).
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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.