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 <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10
Solution
/**
* @param {number[]} jobDifficulty
* @param {number} d
* @return {number}
*/
var minDifficulty = function(jobDifficulty, d) {
var dp = Array(jobDifficulty.length).fill(0).map(() => Array(d));
return helper(jobDifficulty, d, 0, dp);
};
var helper = function(jobs, d, index, dp) {
if (jobs.length < d) return -1;
if (d === 0 && index === jobs.length) return 0;
if (d === 0) return Number.MAX_SAFE_INTEGER;
if (dp[index][d] !== undefined) return dp[index][d];
var min = Number.MAX_SAFE_INTEGER;
var maxDifficulty = Number.MIN_SAFE_INTEGER;
for (var i = index; i <= jobs.length - d; i++) {
maxDifficulty = Math.max(maxDifficulty, jobs[i]);
min = Math.min(min, maxDifficulty + helper(jobs, d - 1, i + 1, dp));
}
dp[index][d] = min;
return min;
};
Explain:
nope.
Complexity:
- Time complexity : O(n * m).
- Space complexity : O(n * m).