You are given an array jobDifficulty of length n, where each element represents the difficulty of a job scheduled in a specific order. You are also given an integer d representing the number of days you must schedule all jobs.
Each day, you must assign at least one job, and jobs assigned on a day must be a consecutive sequence from the array. The difficulty of a day is defined as the maximum difficulty among the jobs scheduled that day. The total difficulty of the schedule is the sum of each day's difficulty.
Your task is to split the jobs into d days such that the total difficulty is minimized. If it is not possible to schedule all jobs in d days (i.e., n < d), return -1.
Constraints:
-1 if impossible.
The problem is about partitioning the jobDifficulty array into d contiguous segments (days), where each segment has at least one job, and minimizing the sum of the maximum job difficulty in each segment.
A brute-force approach would consider all possible ways to split the array into d segments, compute the sum of maximums for each, and return the minimum. However, the number of possible splits grows exponentially with the array size, making brute-force infeasible for larger inputs.
This problem has overlapping subproblems and optimal substructure, suggesting that dynamic programming (DP) is an effective strategy. By breaking the problem into smaller subproblems—such as "what is the minimum total difficulty for scheduling the first i jobs in k days?"—we can build up the solution efficiently.
The main challenge is efficiently computing the maximum difficulty for each possible segment and managing the DP state transitions.
We use dynamic programming to solve this problem efficiently. Let's break down the approach step by step:
dp[i][k] represent the minimum total difficulty to schedule the first i jobs in k days.i = 0 and k = 0, then dp[0][0] = 0 (no jobs, no days, zero difficulty).i < k, it's impossible to schedule, so set dp[i][k] = inf.dp[i][k], try all possible previous split points j where the last day takes jobs j to i-1 (since arrays are 0-based).j from k-1 to i-1:
j to i-1.dp[i][k] = min(dp[i][k], dp[j][k-1] + max_difficulty).dp[n][d], where n is the length of jobDifficulty.i-1 to k-1 for each day.n < d, return -1 immediately.This DP approach ensures we consider all valid splits and efficiently compute the minimum total difficulty.
Input: jobDifficulty = [6,5,4,3,2,1], d = 2
We need to split the jobs into 2 days. Let's walk through the solution:
dp[i][k] for all i and k, and finally return dp[6][2] = 7.n jobs into d parts is exponential, leading to O(2^n) time complexity.O(n*d) DP states.n previous jobs, leading to O(n^2*d) total time complexity.O(n*d) for the DP table.O(n^2*d) is standard and acceptable for constraints.To solve the Minimum Difficulty of a Job Schedule problem, we use dynamic programming to efficiently explore all valid ways to partition the jobs into days, minimizing the sum of daily maximum difficulties. By carefully defining our DP state and transitions, we avoid redundant calculations and ensure an optimal solution, even for larger inputs. This approach elegantly balances exhaustive search with computational efficiency, making it a classic example of DP in action.
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')] * (d + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
for k in range(1, min(d, i) + 1):
maxd = 0
for j in range(i - 1, k - 2, -1):
maxd = max(maxd, jobDifficulty[j])
if dp[j][k - 1] != float('inf'):
dp[i][k] = min(dp[i][k], dp[j][k - 1] + maxd)
return dp[n][d] if dp[n][d] != float('inf') else -1
#include <vector>
#include <algorithm>
#include <climits>
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(n + 1, vector<int>(d + 1, INT_MAX));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int k = 1; k <= min(d, i); ++k) {
int maxd = 0;
for (int j = i - 1; j >= k - 1; --j) {
maxd = max(maxd, jobDifficulty[j]);
if (dp[j][k - 1] != INT_MAX) {
dp[i][k] = min(dp[i][k], dp[j][k - 1] + maxd);
}
}
}
}
return dp[n][d] == INT_MAX ? -1 : dp[n][d];
}
};
import java.util.*;
class Solution {
public int minDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.length;
if (n < d) return -1;
int[][] dp = new int[n + 1][d + 1];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int k = 1; k <= Math.min(d, i); ++k) {
int maxd = 0;
for (int j = i - 1; j >= k - 1; --j) {
maxd = Math.max(maxd, jobDifficulty[j]);
if (dp[j][k - 1] != Integer.MAX_VALUE) {
dp[i][k] = Math.min(dp[i][k], dp[j][k - 1] + maxd);
}
}
}
}
return dp[n][d] == Integer.MAX_VALUE ? -1 : dp[n][d];
}
}
/**
* @param {number[]} jobDifficulty
* @param {number} d
* @return {number}
*/
var minDifficulty = function(jobDifficulty, d) {
const n = jobDifficulty.length;
if (n < d) return -1;
const dp = Array.from({length: n + 1}, () => Array(d + 1).fill(Infinity));
dp[0][0] = 0;
for (let i = 1; i <= n; ++i) {
for (let k = 1; k <= Math.min(d, i); ++k) {
let maxd = 0;
for (let j = i - 1; j >= k - 1; --j) {
maxd = Math.max(maxd, jobDifficulty[j]);
if (dp[j][k - 1] !== Infinity) {
dp[i][k] = Math.min(dp[i][k], dp[j][k - 1] + maxd);
}
}
}
}
return dp[n][d] === Infinity ? -1 : dp[n][d];
};