Minimum Difficulty of a Job Schedule

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.

Examples

Example 1:

1
2
3
4
5
6
7


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:

1
2
3
4
5


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:

1
2
3
4
5


Input:
jobDifficulty = [1,1,1], d = 3
Output:
 3
Explanation: The schedule is one job per day. total difficulty will be 3.

Solution

This problem is close to Largest Sum of Averages.

Method 1 - Top Down DP

Intuition

Use recursion with memoization to find the minimum difficulty of scheduling jobs over d days. At each step, try every possible split for the current day, and recursively solve for the remaining days. Memoize results to avoid redundant computation.

Approach

Define a recursive function dfs(idx, d) that returns the minimum difficulty to schedule jobs from index idx with d days left. For each possible split, calculate the max difficulty for the current day and add the result of the recursive call for the remaining days. Use a DP table to cache results.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
public:
	int minDifficulty(vector<int>& jobDifficulty, int d) {
		int n = jobDifficulty.size();
		if (n < d) return -1;
		vector<vector<int>> dp(n+1, vector<int>(d+1, -1));
		function<int(int, int)> dfs = [&](int idx, int days) {
			if (days == 0 && idx == n) return 0;
			if (days == 0 || idx == n) return INT_MAX;
			if (dp[idx][days] != -1) return dp[idx][days];
			int curMax = jobDifficulty[idx], minDiff = INT_MAX;
			for (int i = idx; i < n; ++i) {
				curMax = max(curMax, jobDifficulty[i]);
				int temp = dfs(i+1, days-1);
				if (temp != INT_MAX) minDiff = min(minDiff, temp + curMax);
			}
			return dp[idx][days] = minDiff;
		};
		int res = dfs(0, d);
		return res == INT_MAX ? -1 : res;
	}
};

 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
34
35
36
37
38
39
40
41
42
43
44


func minDifficulty(jobDifficulty []int, d int) int {
	n := len(jobDifficulty)
	if n < d {
		return -1
	}
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, d+1)
		for j := range dp[i] {
			dp[i][j] = -1
		}
	}
	var dfs func(idx, days int) int
	dfs = func(idx, days int) int {
		if days == 0 && idx == n {
			return 0
		}
		if days == 0 || idx == n {
			return 1<<31 - 1
		}
		if dp[idx][days] != -1 {
			return dp[idx][days]
		}
		curMax, minDiff := jobDifficulty[idx], 1<<31-1
		for i := idx; i < n; i++ {
			if jobDifficulty[i] > curMax {
				curMax = jobDifficulty[i]
			}
			temp := dfs(i+1, days-1)
			if temp != 1<<31-1 {
				if temp+curMax < minDiff {
					minDiff = temp + curMax
				}
			}
		}
		dp[idx][days] = minDiff
		return minDiff
	}
	res := dfs(0, d)
	if res == 1<<31-1 {
		return -1
	}
	return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public int minDifficulty(int[] jobDifficulty, int d) {
	int n = jobDifficulty.length;
	if (n < d) return -1;
	int[][] cache = new int[n+1][d+1];
	for (int[] row : cache) Arrays.fill(row, -1);
	return dfs(jobDifficulty, d, 0, cache);
}
private int dfs(int[] jobDifficulty, int d, int idx, int[][] cache) {
	int n = jobDifficulty.length;
	if (d == 0 && idx == n) return 0;
	if (d == 0 || idx == n) return Integer.MAX_VALUE;
	if (cache[idx][d] != -1) return cache[idx][d];
	int curMax = jobDifficulty[idx], min = Integer.MAX_VALUE;
	for (int schedule = idx; schedule < n; schedule++) {
		curMax = Math.max(curMax, jobDifficulty[schedule]);
		int temp = dfs(jobDifficulty, d - 1, schedule + 1, cache);
		if (temp != Integer.MAX_VALUE) {
			min = Math.min(min, temp + curMax);
		}
	}
	return cache[idx][d] = min;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
	fun minDifficulty(jobDifficulty: IntArray, d: Int): Int {
		val n = jobDifficulty.size
		if (n < d) return -1
		val dp = Array(n+1) { IntArray(d+1) { -1 } }
		fun dfs(idx: Int, days: Int): Int {
			if (days == 0 && idx == n) return 0
			if (days == 0 || idx == n) return Int.MAX_VALUE
			if (dp[idx][days] != -1) return dp[idx][days]
			var curMax = jobDifficulty[idx]
			var minDiff = Int.MAX_VALUE
			for (i in idx until n) {
				curMax = maxOf(curMax, jobDifficulty[i])
				val temp = dfs(i+1, days-1)
				if (temp != Int.MAX_VALUE) minDiff = minOf(minDiff, temp + curMax)
			}
			dp[idx][days] = minDiff
			return minDiff
		}
		val res = dfs(0, d)
		return if (res == Int.MAX_VALUE) -1 else res
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
	def minDifficulty(self, jobDifficulty: list[int], d: int) -> int:
		n = len(jobDifficulty)
		if n < d:
			return -1
		from functools import lru_cache
		@lru_cache(maxsize=None)
		def dfs(idx, days):
			if days == 0 and idx == n:
				return 0
			if days == 0 or idx == n:
				return float('inf')
			curMax, minDiff = jobDifficulty[idx], float('inf')
			for i in range(idx, n):
				curMax = max(curMax, jobDifficulty[i])
				temp = dfs(i+1, days-1)
				if temp != float('inf'):
					minDiff = min(minDiff, temp + curMax)
			return minDiff
		res = dfs(0, d)
		return -1 if res == float('inf') else res

 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


impl Solution {
	pub fn min_difficulty(job_difficulty: Vec<i32>, d: i32) -> i32 {
		let n = job_difficulty.len();
		if n < d as usize { return -1; }
		let mut dp = vec![vec![-1; (d+1) as usize]; n+1];
		fn dfs(idx: usize, days: i32, job_difficulty: &Vec<i32>, dp: &mut Vec<Vec<i32>>) -> i32 {
			let n = job_difficulty.len();
			if days == 0 && idx == n { return 0; }
			if days == 0 || idx == n { return i32::MAX; }
			if dp[idx][days as usize] != -1 { return dp[idx][days as usize]; }
			let mut cur_max = job_difficulty[idx];
			let mut min_diff = i32::MAX;
			for i in idx..n {
				cur_max = cur_max.max(job_difficulty[i]);
				let temp = dfs(i+1, days-1, job_difficulty, dp);
				if temp != i32::MAX {
					min_diff = min_diff.min(temp + cur_max);
				}
			}
			dp[idx][days as usize] = min_diff;
			min_diff
		}
		let res = dfs(0, d, &job_difficulty, &mut dp);
		if res == i32::MAX { -1 } else { res }
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


function minDifficulty(jobDifficulty: number[], d: number): number {
	const n = jobDifficulty.length;
	if (n < d) return -1;
	const dp: number[][] = Array.from({length: n+1}, () => Array(d+1).fill(-1));
	function dfs(idx: number, days: number): number {
		if (days === 0 && idx === n) return 0;
		if (days === 0 || idx === n) return Number.POSITIVE_INFINITY;
		if (dp[idx][days] !== -1) return dp[idx][days];
		let curMax = jobDifficulty[idx], minDiff = Number.POSITIVE_INFINITY;
		for (let i = idx; i < n; i++) {
			curMax = Math.max(curMax, jobDifficulty[i]);
			const temp = dfs(i+1, days-1);
			if (temp !== Number.POSITIVE_INFINITY) minDiff = Math.min(minDiff, temp + curMax);
		}
		dp[idx][days] = minDiff;
		return minDiff;
	}
	const res = dfs(0, d);
	return res === Number.POSITIVE_INFINITY ? -1 : res;
}

Complexity

⏰ Time complexity: O(n^2 * d), where n is the number of jobs and d is the number of days.
🧺 Space complexity: O(n * d), for the DP table.

Method 2 - Bottom Up DP

Intuition

Transform the recursive top-down DP into an iterative bottom-up DP. Instead of recursing, fill a DP table where dp[day][i] is the minimum difficulty to schedule jobs from index i in day days. For each day, try every possible split and update the table iteratively.

Approach

Create a DP table of size (d+1) x (n+1). For each day, iterate through all possible job splits, updating the minimum difficulty for each subproblem. Use nested loops to fill the table from the last day to the first.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
	int minDifficulty(vector<int>& jobDifficulty, int d) {
		int n = jobDifficulty.size();
		if (n < d) return -1;
		vector<vector<int>> dp(d+1, vector<int>(n+1, INT_MAX));
		dp[0][n] = 0;
		for (int day = 1; day <= d; ++day) {
			for (int i = 0; i <= n - day; ++i) {
				int curMax = 0;
				for (int j = i; j <= n - day; ++j) {
					curMax = max(curMax, jobDifficulty[j]);
					if (dp[day-1][j+1] != INT_MAX)
						dp[day][i] = min(dp[day][i], dp[day-1][j+1] + curMax);
				}
			}
		}
		return dp[d][0] == INT_MAX ? -1 : dp[d][0];
	}
};

 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
34


func minDifficultyBU(jobDifficulty []int, d int) int {
	n := len(jobDifficulty)
	if n < d {
		return -1
	}
	constMax := 1<<31 - 1
	dp := make([][]int, d+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		for j := range dp[i] {
			dp[i][j] = constMax
		}
	}
	dp[0][n] = 0
	for day := 1; day <= d; day++ {
		for i := 0; i <= n-day; i++ {
			curMax := 0
			for j := i; j <= n-day; j++ {
				if jobDifficulty[j] > curMax {
					curMax = jobDifficulty[j]
				}
				if dp[day-1][j+1] != constMax {
					if dp[day][i] > dp[day-1][j+1]+curMax {
						dp[day][i] = dp[day-1][j+1]+curMax
					}
				}
			}
		}
	}
	if dp[d][0] == constMax {
		return -1
	}
	return dp[d][0]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


public int minDifficultyBU(int[] jobDifficulty, int d) {
	int n = jobDifficulty.length;
	if (n < d) return -1;
	int[][] dp = new int[d+1][n+1];
	for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
	dp[0][n] = 0;
	for (int day = 1; day <= d; day++) {
		for (int i = 0; i <= n - day; i++) {
			int curMax = 0;
			for (int j = i; j <= n - day; j++) {
				curMax = Math.max(curMax, jobDifficulty[j]);
				if (dp[day-1][j+1] != Integer.MAX_VALUE)
					dp[day][i] = Math.min(dp[day][i], dp[day-1][j+1] + curMax);
			}
		}
	}
	return dp[d][0] == Integer.MAX_VALUE ? -1 : dp[d][0];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


fun minDifficultyBU(jobDifficulty: IntArray, d: Int): Int {
	val n = jobDifficulty.size
	if (n < d) return -1
	val dp = Array(d+1) { IntArray(n+1) { Int.MAX_VALUE } }
	dp[0][n] = 0
	for (day in 1..d) {
		for (i in 0..(n-day)) {
			var curMax = 0
			for (j in i..(n-day)) {
				curMax = maxOf(curMax, jobDifficulty[j])
				if (dp[day-1][j+1] != Int.MAX_VALUE)
					dp[day][i] = minOf(dp[day][i], dp[day-1][j+1] + curMax)
			}
		}
	}
	return if (dp[d][0] == Int.MAX_VALUE) -1 else dp[d][0]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
	def minDifficultyBU(self, jobDifficulty: list[int], d: int) -> int:
		n = len(jobDifficulty)
		if n < d:
			return -1
		dp = [[float('inf')] * (n+1) for _ in range(d+1)]
		dp[0][n] = 0
		for day in range(1, d+1):
			for i in range(n-day+1):
				curMax = 0
				for j in range(i, n-day+1):
					curMax = max(curMax, jobDifficulty[j])
					if dp[day-1][j+1] != float('inf'):
						dp[day][i] = min(dp[day][i], dp[day-1][j+1] + curMax)
		return -1 if dp[d][0] == float('inf') else dp[d][0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


impl Solution {
	pub fn min_difficulty_bu(job_difficulty: Vec<i32>, d: i32) -> i32 {
		let n = job_difficulty.len();
		if n < d as usize { return -1; }
		let mut dp = vec![vec![i32::MAX; n+1]; (d+1) as usize];
		dp[0][n] = 0;
		for day in 1..=d as usize {
			for i in 0..=n-day {
				let mut cur_max = 0;
				for j in i..=n-day {
					cur_max = cur_max.max(job_difficulty[j]);
					if dp[day-1][j+1] != i32::MAX {
						dp[day][i] = dp[day][i].min(dp[day-1][j+1] + cur_max);
					}
				}
			}
		}
		if dp[d as usize][0] == i32::MAX { -1 } else { dp[d as usize][0] }
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


function minDifficultyBU(jobDifficulty: number[], d: number): number {
	const n = jobDifficulty.length;
	if (n < d) return -1;
	const dp: number[][] = Array.from({length: d+1}, () => Array(n+1).fill(Infinity));
	dp[0][n] = 0;
	for (let day = 1; day <= d; day++) {
		for (let i = 0; i <= n-day; i++) {
			let curMax = 0;
			for (let j = i; j <= n-day; j++) {
				curMax = Math.max(curMax, jobDifficulty[j]);
				if (dp[day-1][j+1] !== Infinity)
					dp[day][i] = Math.min(dp[day][i], dp[day-1][j+1] + curMax);
			}
		}
	}
	return dp[d][0] === Infinity ? -1 : dp[d][0];
}

Complexity

⏰ Time complexity: O(n^2 * d), where n is the number of jobs and d is the number of days.
🧺 Space complexity: O(n * d), for the DP table.

Problem#

Examples#

Solution#

Method 1 - Top Down DP#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Bottom Up DP#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Solution

Method 1 - Top Down DP

Intuition

Approach

Code

Complexity

Method 2 - Bottom Up DP

Intuition

Approach

Code

Complexity