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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
/** | |
Framework (Top-Down: Memorization) | |
1. function | |
dp[i][day]: min diff, starts ith job, with day | |
dp[0][1]: answer | |
2. relation | |
min(hardest + dp[i+1][j+1]), 1 < j < n - day | |
3. base | |
(day == d) max(jobs[i..]) | |
*/ | |
int D, n; | |
vector<int> jobs; | |
vector<int> hardestRemain; | |
vector<vector<int>> memo; | |
int dp(int i, int day){ | |
// base | |
if(day == D) | |
return hardestRemain[i]; | |
if(memo[i][day] == - 1){ | |
int limit = n - (D - day); | |
int ans = 10001; | |
int hardest = 0; | |
for(int j = i; j < limit; j++){ | |
hardest = max(hardest, jobs[j]); | |
ans = min(ans, dp(j + 1, day + 1) + hardest); | |
} | |
memo[i][day] = ans; | |
} | |
return memo[i][day]; | |
} | |
int minDifficulty(vector<int>& jobDifficulty, int d) { | |
// make global | |
D = d; | |
jobs = jobDifficulty; | |
n = jobs.size(); | |
hardestRemain.resize(n); | |
memo.resize(n+1, vector<int>(d+1, -1)); | |
// edge case | |
if(d > n) return -1; | |
// prepare hardest remain | |
for(int i = n - 1; i >= 0; i--){ | |
hardestRemain[i] = jobs[i]; | |
if(i < n - 1) hardestRemain[i] = max(hardestRemain[i+1], hardestRemain[i]); | |
} | |
return dp(0, 1); | |
} | |
}; |
No comments:
Post a Comment