Minimum Difficulty of a Job Schedule solution and explanation
Google
9 more videos on this problem
Minimum Difficulty of a Job Schedule | Recursion | Memoization | Amazon | Leetcode 1335codestorywithMIK · 30:52 · 103K views
Minimum Difficulty of a Job Schedule - Leetcode 1335 - PythonNeetCodeIO · 13:41 · 22K views
1335. Minimum Difficulty of a Job ScheduleAslan Tashtanov · 11:38 · 15K views
Minimum Difficulty of a Job Schedule | Bottom Up | Amazon | Leetcode 1335codestorywithMIK · 28:28 · 5K views
LeetCode 1335. Minimum Difficulty of a Job Schedule Explanation and Solutionhappygirlzt · 11:46 · 5K views
LeetCode 1335. Minimum Difficulty of a Job ScheduleHappy Coding · 17:51 · 5K views
Amazon Coding Interview Question | Leetcode 1335 | Minimum Difficulty of a Job ScheduleWorkWithGoogler · 16:14 · 4K views
1335. Minimum Difficulty of a Job Schedule | DP - 3 WaysAryan Mittal · 32:24 · 3K views
Leetcode 1335 Minimum Difficulty of a Job Schedule | Coding Decoded SDE SheetCoding Decoded · 10:30 · 3K views
1335 || Minimum Difficulty of a Job Schedule || leetcode || Dynamic Programming || Partition DpCode With U-DAY · 23:24 · 259 views
The problem
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 <= 10
Approach overview
Problem 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 1: Dynamic Programming with Bottom-Up Approach
This approach uses a dynamic programming (DP) table to calculate the minimum difficulty schedule. The DP table is constructed such that dp[i][j] represents the minimum difficulty for scheduling the first i jobs in j days. We aim to fill this DP table using a bottom-up approach, iterating over all possible job and day combinations. For each combination, we calculate the scenario where the last day covers a range of jobs and obtains the minimum difficulty possible.
from typing import List
class Solution:
def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
n = len(jobDifficulty)
if n < d:
return -1
dp = [[float('inf')] * (n + 1) for _ in range(d + 1)]
dp[0][0] = 0
for day in range(1, d + 1):
for job in range(day, n + 1):
max_diff = 0
for k in range(job, day - 1, -1):
max_diff = max(max_diff, jobDifficulty[k - 1])
dp[day][job] = min(dp[day][job], dp[day - 1][k - 1] + max_diff)
return dp[d][n]
# Usage Example:
# sol = Solution()
# jobDifficulty = [6, 5, 4, 3, 2, 1]
# d = 2
# print(sol.minDifficulty(jobDifficulty, d)) # Output: 7import java.util.Arrays;
public class Solution {
public int minDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.length;
if (n < d) return -1;
int[][] dp = new int[d + 1][n + 1];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
dp[0][0] = 0;
for (int day = 1; day <= d; ++day) {
for (int job = day; job <= n; ++job) {
int maxDifficulty = 0;
for (int k = job; k >= day; --k) {
maxDifficulty = Math.max(maxDifficulty, jobDifficulty[k - 1]);
if (dp[day - 1][k - 1] != Integer.MAX_VALUE)
dp[day][job] = Math.min(dp[day][job], dp[day - 1][k - 1] + maxDifficulty);
}
}
}
return dp[d][n];
}
// Usage Example:
// public static void main(String[] args) {
// Solution sol = new Solution();
// int[] jobDifficulty = {6,5,4,3,2,1};
// int d = 2;
// System.out.println(sol.minDifficulty(jobDifficulty, d)); // Output: 7
// }
public static void main(String[] args) {
Solution sol = new Solution();
int[] jobDifficulty = {6,5,4,3,2,1};
int d = 2;
int result = sol.minDifficulty(jobDifficulty, d);
System.out.println(result); // Output: 7
}
}#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
class Solution {
public:
int minDifficulty(vector<int>& jobDifficulty, int d) {
int n = jobDifficulty.size();
if (n < d) return -1;
vector<vector<int>> dp(d + 1, vector<int>(n + 1, INT_MAX));
dp[0][0] = 0;
for (int day = 1; day <= d; ++day) {
for (int job = day; job <= n; ++job) {
int maxDifficulty = 0;
for (int k = job; k >= day; --k) {
maxDifficulty = max(maxDifficulty, jobDifficulty[k - 1]);
dp[day][job] = min(dp[day][job], dp[day - 1][k - 1] + maxDifficulty);
}
}
}
return dp[d][n];
}
};
// Usage Example:
// int main() {
// Solution sol;
// vector<int> jobDifficulty = {6,5,4,3,2,1};
// int d = 2;
// int result = sol.minDifficulty(jobDifficulty, d);
// // Output: 7
// }var minDifficulty = function(jobDifficulty, d) {
const n = jobDifficulty.length;
if (n < d) return -1;
const dp = Array.from({ length: d + 1 }, () => Array(n + 1).fill(Infinity));
dp[0][0] = 0;
for (let day = 1; day <= d; ++day) {
for (let job = day; job <= n; ++job) {
let maxDifficulty = 0;
for (let k = job; k >= day; --k) {
maxDifficulty = Math.max(maxDifficulty, jobDifficulty[k - 1]);
dp[day][job] = Math.min(dp[day][job], dp[day - 1][k - 1] + maxDifficulty);
}
}
}
return dp[d][n];
};
// Usage Example:
// let jobDifficulty = [6, 5, 4, 3, 2, 1];
// let d = 2;
// console.log(minDifficulty(jobDifficulty, d)); // Output: 7#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int minDifficulty(int* jobDifficulty, int jobDifficultySize, int d) {
if (jobDifficultySize < d) return -1;
int dp[d+1][jobDifficultySize+1];
for (int i = 0; i <= d; ++i) {
for (int j = 0; j <= jobDifficultySize; ++j) {
dp[i][j] = INT_MAX;
}
}
dp[0][0] = 0;
for (int day = 1; day <= d; ++day) {
for (int job = day; job <= jobDifficultySize; ++job) {
int maxDifficulty = 0;
for (int k = job; k >= day; --k) {
maxDifficulty = (maxDifficulty > jobDifficulty[k-1]) ? maxDifficulty : jobDifficulty[k-1];
dp[day][job] = (dp[day][job] < dp[day-1][k-1] + maxDifficulty) ? dp[day][job] : dp[day-1][k-1] + maxDifficulty;
}
}
}
return dp[d][jobDifficultySize];
}
int main() {
int jobDifficulty[] = {6,5,4,3,2,1};
int d = 2;
printf("%d\n", minDifficulty(jobDifficulty, 6, d)); // Output: 7
return 0;
}using System;
public class Solution {
public int MinDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.Length;
if (n < d) return -1;
int[,] dp = new int[d + 1, n + 1];
for (int i = 0; i <= d; i++)
for (int j = 0; j <= n; j++)
dp[i, j] = int.MaxValue;
dp[0, 0] = 0;
for (int day = 1; day <= d; ++day) {
for (int job = day; job <= n; ++job) {
int maxDifficulty = 0;
for (int k = job; k >= day; --k) {
maxDifficulty = Math.Max(maxDifficulty, jobDifficulty[k - 1]);
dp[day, job] = Math.Min(dp[day, job], dp[day - 1, k - 1] + maxDifficulty);
}
}
}
return dp[d, n];
}
// Example usage:
// public static void Main(string[] args) {
// Solution sol = new Solution();
// int[] jobDifficulty = {6,5,4,3,2,1};
// int d = 2;
// Console.WriteLine(sol.MinDifficulty(jobDifficulty, d)); // Output: 7
// }
}The Python solution constructs and updates the DP table efficiently using list comprehensions and nested loops, reflecting the same bottom-up approach to calculate the minimal schedule difficulty for given jobs.
Time Complexity: O(n2d)
Space Complexity: O(nd)
Approach 2: Recursive Approach with Memoization
This approach is based on recursion with memoization. The main idea is to use a recursive function to find the minimum difficulty from a given starting index, splitting the jobs over the remaining days. For each recursive call, consider different partitions for the first day's job and compute the best possible schedule using range maximum queries and storing results to avoid redundant calculations.
from functools import lru_cache
from typing import List
class Solution:
def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
n = len(jobDifficulty)
if n < d:
return -1
@lru_cache(None)
def dfs(idx, days):
if days == 1:
return max(jobDifficulty[idx:])
max_diff, result = 0, float('inf')
for i in range(idx, n - days + 1):
max_diff = max(max_diff, jobDifficulty[i])
result = min(result, max_diff + dfs(i + 1, days - 1))
return result
return dfs(0, d)
# Usage Example:
# sol = Solution()
# jobDifficulty = [6, 5, 4, 3, 2, 1]
# d = 2
# print(sol.minDifficulty(jobDifficulty, d)) # Output: 7import java.util.Arrays;
public class Solution {
int[][] memo;
private int dfs(int[] jobDifficulty, int d, int idx) {
if (d == 1) {
int max = 0;
for (int i = idx; i < jobDifficulty.length; i++)
max = Math.max(max, jobDifficulty[i]);
return max;
}
if (memo[d][idx] != -1) return memo[d][idx];
int maxDiff = 0;
int result = Integer.MAX_VALUE;
for (int i = idx; i <= jobDifficulty.length - d; ++i) {
maxDiff = Math.max(maxDiff, jobDifficulty[i]);
result = Math.min(result, maxDiff + dfs(jobDifficulty, d - 1, i + 1));
}
return memo[d][idx] = result;
}
public int minDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.length;
if (n < d) return -1;
memo = new int[d + 1][n];
for (int[] row : memo) Arrays.fill(row, -1);
return dfs(jobDifficulty, d, 0);
}
// Usage Example:
// public static void main(String[] args) {
// Solution sol = new Solution();
// int[] jobDifficulty = {6,5,4,3,2,1};
// int d = 2;
// System.out.println(sol.minDifficulty(jobDifficulty, d)); // Output: 7
// }
public static void main(String[] args) {
Solution sol = new Solution();
int[] jobDifficulty = {6,5,4,3,2,1};
int d = 2;
int result = sol.minDifficulty(jobDifficulty, d);
System.out.println(result); // Output: 7
}
}#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
class Solution {
int memo[11][301];
int dfs(vector<int>& jobDifficulty, int n, int d, int idx) {
if (d == 1) {
return *max_element(jobDifficulty.begin() + idx, jobDifficulty.end());
}
if (memo[d][idx] != -1) return memo[d][idx];
int maxDiff = 0, result = INT_MAX;
for (int i = idx; i <= n - d; ++i) {
maxDiff = max(maxDiff, jobDifficulty[i]);
result = min(result, maxDiff + dfs(jobDifficulty, n, d - 1, i + 1));
}
return memo[d][idx] = result;
}
public:
int minDifficulty(vector<int>& jobDifficulty, int d) {
int n = jobDifficulty.size();
if (n < d) return -1;
memset(memo, -1, sizeof(memo));
return dfs(jobDifficulty, n, d, 0);
}
};
// Usage Example:
// int main() {
// Solution sol;
// vector<int> jobDifficulty = {6,5,4,3,2,1};
// int d = 2;
// int result = sol.minDifficulty(jobDifficulty, d);
// // Output: 7
// }const minDifficulty = (jobDifficulty, d) => {
const n = jobDifficulty.length;
if (n < d) return -1;
const memo = Array.from({ length: d + 1 }, () => Array(n).fill(-1));
const dfs = (idx, days) => {
if (days === 1) return Math.max(...jobDifficulty.slice(idx));
if (memo[days][idx] !== -1) return memo[days][idx];
let maxDiff = 0;
let result = Infinity;
for (let i = idx; i <= n - days; ++i) {
maxDiff = Math.max(maxDiff, jobDifficulty[i]);
result = Math.min(result, maxDiff + dfs(i + 1, days - 1));
}
return memo[days][idx] = result;
}
return dfs(0, d);
};
// Usage Example:
// let jobDifficulty = [6,5,4,3,2,1];
// let d = 2;
// console.log(minDifficulty(jobDifficulty, d)); // Output: 7#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
int min(int a, int b) {
return a < b ? a : b;
}
int memo[11][301];
int dfs(int *jobDifficulty, int n, int d, int idx) {
if (d == 1) {
int maxDiff = jobDifficulty[idx];
for (int i = idx + 1; i < n; ++i)
if (jobDifficulty[i] > maxDiff)
maxDiff = jobDifficulty[i];
return maxDiff;
}
if (memo[d][idx] != -1) return memo[d][idx];
int maxDiff = 0;
int result = INT_MAX;
for (int i = idx; i <= n - d; ++i) {
if (jobDifficulty[i] > maxDiff) maxDiff = jobDifficulty[i];
result = min(result, maxDiff + dfs(jobDifficulty, n, d - 1, i + 1));
}
return memo[d][idx] = result;
}
int minDifficulty(int *jobDifficulty, int jobDifficultySize, int d) {
if (jobDifficultySize < d) return -1;
memset(memo, -1, sizeof(memo));
return dfs(jobDifficulty, jobDifficultySize, d, 0);
}
int main() {
int jobDifficulty[] = {6,5,4,3,2,1};
int d = 2;
printf("%d\n", minDifficulty(jobDifficulty, 6, d)); // Output: 7
return 0;
}using System;
using System.Linq;
public class Solution {
int[,] memo;
private int Dfs(int[] jobDifficulty, int d, int idx) {
if (d == 1) {
return jobDifficulty.Skip(idx).Max();
}
if (memo[d, idx] != -1) return memo[d, idx];
int maxDiff = 0, result = int.MaxValue;
for (int i = idx; i <= jobDifficulty.Length - d; ++i) {
maxDiff = Math.Max(maxDiff, jobDifficulty[i]);
result = Math.Min(result, maxDiff + Dfs(jobDifficulty, d - 1, i + 1));
}
return memo[d, idx] = result;
}
public int MinDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.Length;
if (n < d) return -1;
memo = new int[d + 1, n];
for (int i = 0; i <= d; i++)
for (int j = 0; j < n; j++)
memo[i, j] = -1;
return Dfs(jobDifficulty, d, 0);
}
// Example usage:
// public static void Main(string[] args) {
// Solution sol = new Solution();
// int[] jobDifficulty = {6,5,4,3,2,1};
// int d = 2;
// Console.WriteLine(sol.MinDifficulty(jobDifficulty, d)); // Output: 7
// }
}This Python solution uses memoized DFS with functools' lru_cache to avoid recomputations, minimizing the scheduling difficulty using recursive optimal partitioning.
Time Complexity: O(n2d)
Space Complexity: O(nd)
Approach 3: Dynamic Programming
We define f[i][j] as the minimum difficulty to finish the first i jobs within j days. Initially f[0][0] = 0, and all other f[i][j] are infty.
For the j-th day, we can choose to finish jobs [k,..i] on this day. Therefore, we have the following state transition equation:
$
f[i][j] = min_{k \in [1,i]} {f[k-1][j-1] + max_{k leq t leq i} {jobDifficulty[t]}}
The final answer is f[n][d].
The time complexity is O(n^2 times d), and the space complexity is O(n times d). Here n and d$ are the number of jobs and the number of days respectively.
function minDifficulty(jobDifficulty: number[], d: number): number {
const n = jobDifficulty.length;
const inf = 1 << 30;
const f: number[][] = new Array(n + 1).fill(0).map(() => new Array(d + 1).fill(inf));
f[0][0] = 0;
for (let i = 1; i <= n; ++i) {
for (let j = 1; j <= Math.min(d, i); ++j) {
let mx = 0;
for (let 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 ? f[n][d] : -1;
}func minDifficulty(jobDifficulty []int, d int) int {
n := len(jobDifficulty)
f := make([][]int, n+1)
const inf = 1 << 30
for i := range f {
f[i] = make([]int, d+1)
for j := range f[i] {
f[i][j] = inf
}
}
f[0][0] = 0
for i := 1; i <= n; i++ {
for j := 1; j <= min(d, i); j++ {
mx := 0
for k := i; k > 0; k-- {
mx = max(mx, jobDifficulty[k-1])
f[i][j] = min(f[i][j], f[k-1][j-1]+mx)
}
}
}
if f[n][d] == inf {
return -1
}
return f[n][d]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Bottom-Up Approach | Time Complexity: O(n2d) Space Complexity: O(nd) |
| Recursive Approach with Memoization | Time Complexity: O(n2d) Space Complexity: O(nd) |
| Dynamic Programming | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Difficulty of a Job Schedule easy or hard?
Minimum Difficulty of a Job Schedule is classified as a Hard problem because it requires recognizing a partition dynamic programming pattern. Efficient solutions require defining the correct DP state and optimizing overlapping subproblems.
Minimum Difficulty of a Job Schedule Python/Java solution
Both Python and Java implementations typically use a 2D DP array or memoized recursion. The algorithm iterates over possible split points for each day and tracks the maximum job difficulty in the current segment, resulting in O(n^2 * d) time complexity.
How to solve Minimum Difficulty of a Job Schedule in O(n^2 * d)?
Use dynamic programming where dp[i][k] stores the minimum difficulty to schedule the first i jobs in k days. For each state, iterate backward to determine which jobs belong to the last day and track the maximum difficulty of that segment. Combine it with dp[j-1][k-1] to compute the minimum total difficulty.
What is the best approach for Minimum Difficulty of a Job Schedule?
Dynamic programming is the best approach. Define a state representing the minimum difficulty to schedule the first i jobs in k days and try all possible partitions for the last day. Both memoized recursion and bottom-up DP achieve O(n^2 * d) time and O(n * d) space.
Is Minimum Difficulty of a Job Schedule asked at Google/Amazon/Meta?
Partition-based dynamic programming problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants involving job scheduling, partition DP, or minimizing segment costs are common in high-level algorithm interviews.
What data structure is used in Minimum Difficulty of a Job Schedule?
The main data structures are arrays and a 2D dynamic programming table. The DP table stores intermediate results for combinations of job indices and remaining days, while the jobDifficulty array is scanned to compute segment maximums.
What is the time complexity of Minimum Difficulty of a Job Schedule?
The optimal dynamic programming solution runs in O(n^2 * d) time. For each day and job index, the algorithm iterates through possible partition points while maintaining the maximum difficulty for the current segment.