You want to schedule a list of jobs in d
days. Jobs are dependent (i.e To work on the i-th
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 in that day.
Given an array of integers jobDifficulty
and an integer d
. The difficulty of the i-th
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.
Example 4:
Input: jobDifficulty = [7,1,7,1,7,1], d = 3 Output: 15
Example 5:
Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6 Output: 843
Constraints:
1 <= jobDifficulty.length <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10
Related Topics:
Dynamic Programming
Let dp[d][i]
be the answer for the subproblem with d
days at i
th job.
Let mx[i][j]
be the maximum value in A[i..j]
.
dp[d][i] = min( dp[d-1][j-1] + mx[j][i] | d-1 <= j <= i )
// OJ: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
// Author: github.com/lzl124631x
// Time: O(N^2 * D)
// Space: O(N^2 + ND)
class Solution {
typedef long long LL;
inline void setMin(LL &a, LL b) { a = min(a, b); }
public:
int minDifficulty(vector<int>& A, int D) {
int N = A.size();
if (D > N) return -1;
vector<vector<LL>> mx(N, vector<LL>(N)), dp(D + 1, vector<LL>(N, 1e9));
for (int i = 0; i < N; ++i) {
for (int j = i; j < N; ++j) mx[i][j] = *max_element(A.begin() + i, A.begin() + j + 1);
}
for (int i = 0; i < N; ++i) dp[1][i] = mx[0][i];
for (int d = 2; d <= D; ++d) {
for (int i = d - 1; i < N; ++i) {
for (int j = d - 1; j <= i; ++j) {
setMin(dp[d][i], dp[d - 1][j - 1] + mx[j][i]);
}
}
}
return dp[D][N - 1];
}
};
We can compute the mx
while computing dp
instead of computing mx
array beforehand.
// OJ: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
// Author: github.com/lzl124631x
// Time: O(N^2 * D)
// Space: O(ND)
class Solution {
typedef long long LL;
inline void setMin(LL &a, LL b) { a = min(a, b); }
public:
int minDifficulty(vector<int>& A, int D) {
int N = A.size(), inf = 1e9;
if (D > N) return -1;
vector<vector<LL>> dp(D + 1, vector<LL>(N, inf));
for (int i = 0; i < N; ++i) dp[1][i] = i == 0 ? A[0] : max(dp[1][i - 1], (LL)A[i]);
for (int d = 2; d <= D; ++d) {
for (int i = d - 1; i < N; ++i) {
int mx = 0;
for (int j = i; j >= d - 1; --j) {
mx = max(mx, A[j]);
setMin(dp[d][i], dp[d - 1][j - 1] + mx);
}
}
}
return dp[D][N - 1];
}
};
Since dp[d][i]
is dependent on dp[d-1][j-1]
and j <= i
, we can flip the loop direction and just need 1D dp
array.
// OJ: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
// Author: github.com/lzl124631x
// Time: O(NND)
// Space: O(N)
class Solution {
typedef long long LL;
inline void setMin(LL &a, LL b) { a = min(a, b); }
public:
int minDifficulty(vector<int>& A, int D) {
int N = A.size(), inf = 1e9;
if (D > N) return -1;
vector<LL> dp(N);
for (int i = 0; i < N; ++i) dp[i] = i == 0 ? A[0] : max(dp[i - 1], (LL)A[i]);
for (int d = 2; d <= D; ++d) {
for (int i = N - 1; i >= d - 1; --i) {
int mx = 0;
dp[i] = inf;
for (int j = i; j >= d - 1; --j) {
mx = max(mx, A[j]);
setMin(dp[i], dp[j - 1] + mx);
}
}
}
return dp[N - 1];
}
};