forked from MukulCode/CodingClubIndia
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathjob-scheduling-problem.cpp
More file actions
33 lines (31 loc) · 901 Bytes
/
job-scheduling-problem.cpp
File metadata and controls
33 lines (31 loc) · 901 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int dp[305][15];
int find(vector<int> &diff, int d, int i) {
if(d == 1) {
if(i == diff.size()) {
return INT_MAX / 4;
}
int mx = -1;
for(int j = i; j < diff.size(); j++) {
mx = max(diff[j], mx);
}
return mx;
}
if(dp[i][d] != -1) {
return dp[i][d];
}
int mx = -1;
int ans = INT_MAX / 2;
for(int j = i; j < diff.size() - d + 1; j++) {
mx = max(diff[j], mx);
ans = min(ans, mx + find(diff, d - 1, j + 1));
}
return dp[i][d] = ans;
}
int minDifficulty(vector<int>& jobDifficulty, int d) {
memset(dp, -1, sizeof dp);
int ans = find(jobDifficulty, d, 0);
return (ans >= INT_MAX / 2 ? -1 : ans);
}
};