This approach uses a dynamic programming (DP) table to calculate the minimum difficulty schedule. The DP table is constructed such that dp[i][j] represents the minimum difficulty for scheduling the first i jobs in j days. We aim to fill this DP table using a bottom-up approach, iterating over all possible job and day combinations. For each combination, we calculate the scenario where the last day covers a range of jobs and obtains the minimum difficulty possible.
Time Complexity: O(n2d), where n is the length of jobDifficulty and d is the number of days.
Space Complexity: O(nd), due to the storage of minimum difficulties in the DP table.
1var minDifficulty = function(jobDifficulty, d) {
2 const n = jobDifficulty.length;
3 if (n < d) return -1;
4 const dp = Array.from({ length: d + 1 }, () => Array(n + 1).fill(Infinity));
5 dp[0][0] = 0;
6
7 for (let day = 1; day <= d; ++day) {
8 for (let job = day; job <= n; ++job) {
9 let maxDifficulty = 0;
10 for (let k = job; k >= day; --k) {
11 maxDifficulty = Math.max(maxDifficulty, jobDifficulty[k - 1]);
12 dp[day][job] = Math.min(dp[day][job], dp[day - 1][k - 1] + maxDifficulty);
13 }
14 }
15 }
16 return dp[d][n];
17};
18
19// Usage Example:
20// let jobDifficulty = [6, 5, 4, 3, 2, 1];
21// let d = 2;
22// console.log(minDifficulty(jobDifficulty, d)); // Output: 7
23This JavaScript solution involves setting up a DP array using Array.from to create the DP table. It iterates through possible configurations of job partitions over days similarly to other languages but adheres to JavaScript syntax.
This approach is based on recursion with memoization. The main idea is to use a recursive function to find the minimum difficulty from a given starting index, splitting the jobs over the remaining days. For each recursive call, consider different partitions for the first day's job and compute the best possible schedule using range maximum queries and storing results to avoid redundant calculations.
Time Complexity: O(n2d), with memoization reducing redundant calculations.
Space Complexity: O(nd), storing calculated subproblems and recursion frames.
1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4#include <string.h>
5
6int min(int a, int b) {
7 return a < b ? a : b;
8}
9
10int memo[11][301];
11int dfs(int *jobDifficulty, int n, int d, int idx) {
12 if (d == 1) {
13 int maxDiff = jobDifficulty[idx];
14 for (int i = idx + 1; i < n; ++i)
15 if (jobDifficulty[i] > maxDiff)
16 maxDiff = jobDifficulty[i];
17 return maxDiff;
18 }
19 if (memo[d][idx] != -1) return memo[d][idx];
20
21 int maxDiff = 0;
22 int result = INT_MAX;
23 for (int i = idx; i <= n - d; ++i) {
24 if (jobDifficulty[i] > maxDiff) maxDiff = jobDifficulty[i];
25 result = min(result, maxDiff + dfs(jobDifficulty, n, d - 1, i + 1));
26 }
27 return memo[d][idx] = result;
28}
29
30int minDifficulty(int *jobDifficulty, int jobDifficultySize, int d) {
31 if (jobDifficultySize < d) return -1;
32 memset(memo, -1, sizeof(memo));
33 return dfs(jobDifficulty, jobDifficultySize, d, 0);
34}
35
36int main() {
37 int jobDifficulty[] = {6,5,4,3,2,1};
38 int d = 2;
39 printf("%d\n", minDifficulty(jobDifficulty, 6, d)); // Output: 7
40 return 0;
41}This implementation utilizes a recursive depth-first search (DFS) function to handle the subproblem, memorizing results as each substate is calculated. The search accumulates the maximum difficulty for each possible partition of jobs for current day.