Minimum Difficulty of a Job Schedule
Problem
You must finish a list of jobs in the given order over exactly d days, doing at least one job every day. A day's difficulty is the maximum difficulty among the jobs done that day, and the schedule's total difficulty is the sum of the daily difficulties. Return the minimum possible total, or -1 if there are fewer jobs than days (constraints: up to 300 jobs with difficulties 0..1000, and 1 ≤ d ≤ 10).
jobDifficulty = [6,5,4,3,2,1], d = 27def min_difficulty(job_difficulty, d):
n = len(job_difficulty)
if n < d:
return -1
INF = float("inf")
dp = [[INF] * (n + 1) for _ in range(d + 1)]
dp[0][0] = 0
for k in range(1, d + 1):
for i in range(k, n + 1):
mx = 0
for j in range(i - 1, k - 2, -1):
mx = max(mx, job_difficulty[j])
cand = dp[k - 1][j] + mx
if cand < dp[k][i]:
dp[k][i] = cand
return dp[d][n]function minDifficulty(jobDifficulty, d) {
const n = jobDifficulty.length;
if (n < d) return -1;
const INF = Infinity;
const dp = Array.from({ length: d + 1 }, () => new Array(n + 1).fill(INF));
dp[0][0] = 0;
for (let k = 1; k <= d; k++) {
for (let i = k; i <= n; i++) {
let mx = 0;
for (let j = i - 1; j >= k - 1; j--) {
mx = Math.max(mx, jobDifficulty[j]);
dp[k][i] = Math.min(dp[k][i], dp[k - 1][j] + mx);
}
}
}
return dp[d][n];
}int minDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.length;
if (n < d) return -1;
int INF = 1_000_000_000;
int[][] dp = new int[d + 1][n + 1];
for (int[] row : dp) Arrays.fill(row, INF);
dp[0][0] = 0;
for (int k = 1; k <= d; k++) {
for (int i = k; i <= n; i++) {
int mx = 0;
for (int j = i - 1; j >= k - 1; j--) {
mx = Math.max(mx, jobDifficulty[j]);
dp[k][i] = Math.min(dp[k][i], dp[k - 1][j] + mx);
}
}
}
return dp[d][n];
}int minDifficulty(vector<int>& jobDifficulty, int d) {
int n = jobDifficulty.size();
if (n < d) return -1;
const int INF = 1000000000;
vector<vector<int>> dp(d + 1, vector<int>(n + 1, INF));
dp[0][0] = 0;
for (int k = 1; k <= d; k++) {
for (int i = k; i <= n; i++) {
int mx = 0;
for (int j = i - 1; j >= k - 1; j--) {
mx = max(mx, jobDifficulty[j]);
dp[k][i] = min(dp[k][i], dp[k - 1][j] + mx);
}
}
}
return dp[d][n];
}Explanation
Because jobs must be done in order and every day needs at least one job, a schedule is exactly a partition of the array into d contiguous, non-empty blocks. Each block costs its maximum element, and we want the partition with the smallest sum of block maxima.
Define dp[k][i] = minimum total difficulty to finish the first i jobs in k days. The last day (day k) takes some block of jobs j..i-1, and everything before it must be a valid k-1-day schedule of the first j jobs. So dp[k][i] = min over j of dp[k-1][j] + max(jobs[j..i-1]), with j ranging from k-1 (earlier days need one job each) to i-1.
The small trick that keeps each cell cheap: scan j from i-1 downward while maintaining a running maximum mx of the candidate block. Each time j drops by one, the block grows on the left and mx updates in O(1), so a cell costs O(n) instead of recomputing maxima from scratch.
On the default example [6,5,4,3,2,1] with d = 2: row 1 is just prefix maxima, so every dp[1][i] = 6. In row 2 the best split for the full array leaves only the cheapest job for day 2: dp[2][6] = dp[1][5] + max(jobs[5..5]) = 6 + 1 = 7. Note a greedy "balance the days" idea would happily pay more — the DP tries every split and is the only safe way.
The base case dp[0][0] = 0 with everything else infinite forces day 1 blocks to start at job 0, and if n < d there is no way to give each day a job, so we return -1 immediately.
There are d·n table cells and each scans at most n starts, giving O(d·n²) time and O(d·n) space — comfortably fast for n ≤ 300, d ≤ 10.