DSA problem
Minimum Difficulty of a Job Schedule
You have jobDifficulty — a list of jobs to perform in order — and an integer d representing the number of days you have to finish them. You must complete at least one job per day and you must finish them in the given order: day 1 takes some prefix jobDifficulty[0..i1], day 2 takes the next contiguous block jobDifficulty[i1 + 1..i2], and so on. The difficulty of a day equals the maximum difficulty among the jobs done that day, and the total schedule difficulty is the sum of daily difficulties. Return the minimum total difficulty, or -1 if a valid schedule does not exist (i.e., fewer jobs than days).
The optimization splits a sequence into d contiguous groups, minimizing the sum of per-group maxima. Define dp[i][k] = minimum total difficulty to schedule the first i + 1 jobs in k + 1 days. The recurrence iterates over the last day's starting index j: that last day covers jobDifficulty[j..i] and contributes max(jobDifficulty[j..i]) to the cost. So dp[i][k] = min over j in [k..i] of (dp[j - 1][k - 1] + max(jobDifficulty[j..i])).
The naive evaluation recomputes a max for each (i, j), but you can sweep j from i down to k while maintaining a running max mx, updating it as mx = max(mx, jobDifficulty[j]). This makes each cell O(n) and the overall DP O(n^2 * d).
The base case k = 0 is the prefix max of the first row, dp[i][0] = max(jobDifficulty[0..i]). The answer is dp[n - 1][d - 1], or -1 if n < d. Total: O(n^2 * d) time and O(n * d) space (compressible to O(n) with rolling rows).
Examples
jobDifficulty = [6,5,4,3,2,1], d = 27jobDifficulty = [9,9,9], d = 4-1jobDifficulty = [1,1,1], d = 33Constraints
- 1 <= jobDifficulty.length <= 300
- 0 <= jobDifficulty[i] <= 1000
- 1 <= d <= 10
- Jobs must be done in order: day k's jobs form a contiguous suffix of the unfinished work.
- Each day must contain at least one job.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.