1335. Minimum Difficulty of a Job Schedule
Problem Description
In this problem, we're deciding how to schedule a list of jobs over d
days. Jobs must be completed in a specific order ā to complete the i-th
job, all jobs before it must be done. A job schedule has a "difficulty", which is calculated by summing up the daily difficulties over d
days, and the difficulty of each day is given by the hardest (highest difficulty) job completed on that day.
The goal is to find the job schedule with the minimum total difficulty possible while ensuring that at least one job is finished each day. If you're given a set of jobs, each with its own difficulty level (stored in the array jobDifficulty
), and a certain number of days d
, your task is to find this minimum difficulty. If it's not possible to schedule at least one job per day, the function should return -1
.
To illustrate, imagine you're painting houses, and each house has a different level of effort required. You have a deadline to finish painting d
sets of houses. Each day, you can paint a continuous block of houses, and the difficulty of the day is the hardest house you painted. Your goal is to minimize your total effort over the deadline without taking any days off.
Intuition
The intuitive approach to this kind of problem involves understanding that it's a classic case for dynamic programming, where the optimal solution can be built from the optimal solutions to smaller subproblems.
We create a 2D array f
where f[i][j]
represents the minimum difficulty to complete the first i
jobs in j
days. Initially, we know that f[0][0] = 0
because no difficulty exists if no jobs are done in 0 days. For all other values, we initialize f[i][j]
to infinity (inf
) since we have not yet computed the minimum difficulty for those scenarios.
As we attempt to solve for f[i][j]
, we encounter a choice: which jobs to schedule on the j-th
day? We could select any sequence of jobs ending with the i-th
job to be done on the last day. This selection defines the difficulty of the j-th
day by the hardest job in that sequence. The remaining jobs would have been completed in the previous j-1
days.
So, for each day j
and job i
, we iterate backward through the job list, calculating the difficulty for doing the last k
jobs on day j
, where k
ranges from i
down to 1
. We determine the max job difficulty mx
for the last k
jobs and add it to the previously computed minimum difficulty needed to finish the first k-1
jobs in j-1
days. This gives us the total difficulty if we were to complete the last k
jobs on the current day j
. We keep track of the minimum value for f[i][j]
as we iterate through all possible k
.
The final answer to our scheduling problem is represented by f[n][d]
, which tells us the minimum total difficulty to finish all n
jobs within d
days, based on how the jobs were divided across the days.
Learn more about Dynamic Programming patterns.
Solution Approach
The problem is solved using a dynamic programming algorithm. Let's break down the implementation provided in the reference solution and understand how it aligns with the established approach:
-
Initialization: We create a 2D list
f
that will serve as our DP table withn + 1
rows andd + 1
columns. Each element is initially set to infinity (inf
). The table is used to store the minimum difficulty of completingi
jobs inj
days. We also know thatf[0][0]
should be 0 because no difficulty exists when no jobs are done in 0 days. -
DP Table Population: We use two nested loops to populate this table. The outer loop iterates over the range
[1, n + 1)
to represent the jobs. The inner loop iterates over the range[1, min(d + 1, i + 1))
to represent the days, ensuring we don't try to schedule jobs in more days than we have jobs or days allocated. -
Finding the Minimum Difficulty: Within the inner loop, we introduce another loop iterating from
i
down to1
(backwards). This iteration is critical; for each jobi
and dayj
, it checks all possibilities of completing some lastk
jobs on the current dayj
. The variablemx
holds the maximum job difficulty for thesek
jobs. -
State Transition: For each
k
, we calculate a candidate minimum difficulty by taking the previously computed minimum difficulty fork-1
jobs done inj-1
days (f[k - 1][j - 1]
) and adding the difficulty of completing the currentk
jobs on the current day, represented bymx
. This reflects the state transition equation:1f[i][j] = min(f[i][j], f[k - 1][j - 1] + mx)
Here,
f[i][j]
holds the minimum difficulty fori
jobs done inj
days, and we update it only if we find a lower difficulty than the current stored value. -
Returning the Result: After populating the DP table, we look at
f[n][d]
to see the result. If we find that it's stillinf
, it means that it's not possible to schedule the jobs withind
days, and we should return-1
. Otherwise,f[n][d]
contains the minimum difficulty job schedule.
The key algorithms used here are dynamic programming for solving the optimized subproblems and iterating in reverse order to identify the possible subsets for achieving daily goals. The use of a 2D DP table for storing intermediate results is a common practice in dynamic programming problems to avoid recalculating solutions to subproblems multiple times.
By carefully updating our DP table and checking all possibilities, we guarantee that we find the minimum difficulty job schedule while meeting all the constraints of the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Suppose we have the following job difficulties and days:
1jobDifficulty = [7, 1, 4, 5] 2d = 2
We want to schedule these 4 jobs over 2 days such that the total difficulty of the schedule is minimized.
Step-by-Step Solution:
-
Initialization: We create a 2D list
f
with 5 (n + 1) rows (representing 0 to 4 jobs) and 3 (d + 1) columns (representing 0 to 2 days). This results in a 5x3 matrix initialized to infinity, except forf[0][0]
which is 0.1f = [[0, inf, inf], 2 [inf, inf, inf], 3 [inf, inf, inf], 4 [inf, inf, inf], 5 [inf, inf, inf]]
-
DP Table Population: We iterate over jobs (
i
from 1 to 4) and for each job, over days (j
from 1 up to the current job numberi
without exceeding dayd
). -
Finding the Minimum Difficulty: We perform an inner backward iteration from
i
down to 1 for each job/day combination. -
State Transition: We update the DP array
f
at position[i][j]
.- For
i=1
andj=1
, the only option to schedule the first job on the first day means:1f[1][1] = 7 (which is jobDifficulty[0])
- Moving to
i=2
, we need to check:- If we do job 1 and 2 on day 1, then:
1f[2][1] = max(jobDifficulty[0], jobDifficulty[1]) = max(7, 1) = 7
- If we do job 2 on day 1 and job 1 on day 0 which is not possible, so we ignore it.
- If we do job 1 and 2 on day 1, then:
- Now for
i=2
andj=2
, we need to check:- If we do job 1 on day 1 and job 2 on day 2, then:
1f[2][2] is min(inf, f[1][1] + max(jobDifficulty[1])) = min(inf, 7 + 1) = 8
- If we do job 1 on day 1 and job 2 on day 2, then:
- For
Carrying on with this process till we complete all the jobs, we keep updating f
based on the maximum difficulty of scheduling the last k
jobs on the current day j
and adding it to the minimum difficulty of scheduling the first i - k
jobs on the previous days j - 1
.
- Returning the Result: After populating the table, we check
f[4][2]
for our answer. If it'sinf
, then it's impossible to schedule, but in this case, suppose it is15
, that would be our minimum difficulty to schedule all jobs over 2 days as per our example.
Finally, the DP table f
might look something like this after being populated (with hypothetical values for illustration):
1f = [[0, inf, inf], 2 [7, inf, inf], 3 [7, 8, inf], 4 [10, 11, inf], 5 [15, 12, 15]]
And the result is f[4][2] = 15
, which is the minimum total difficulty to schedule all 4 jobs over 2 days.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minDifficulty(self, job_difficulty: List[int], days: int) -> int:
5 num_jobs = len(job_difficulty)
6 # Initialize DP table with infinity representing impossible scenarios.
7 # dp_table[i][j] will hold the minimum difficulty of scheduling the first i jobs in j days
8 dp_table = [[float('inf')] * (days + 1) for _ in range(num_jobs + 1)]
9 dp_table[0][0] = 0 # Base case: 0 jobs in 0 days has 0 difficulty
10
11 # Loop through each job
12 for i in range(1, num_jobs + 1):
13 # Only consider scheduling up to the minimum of days or jobs done so far
14 for j in range(1, min(days + 1, i + 1)):
15 max_difficulty_on_last_day = 0
16 # Try to end the j-th day with each possible last job
17 for k in range(i, 0, -1):
18 max_difficulty_on_last_day = max(max_difficulty_on_last_day, job_difficulty[k - 1])
19 # Update the DP table by adding the difficulty of the last job to the optimal difficulty of previous jobs in j-1 days
20 dp_table[i][j] = min(dp_table[i][j], dp_table[k - 1][j - 1] + max_difficulty_on_last_day)
21
22 # If the difficulty of scheduling all jobs in d days is infinite, it means it is not possible, thus return -1.
23 # Otherwise, return the calculated difficulty
24 return -1 if dp_table[num_jobs][days] == float('inf') else dp_table[num_jobs][days]
25
1class Solution {
2 public int minDifficulty(int[] jobDifficulty, int d) {
3 final int MAX_DIFFICULTY = Integer.MAX_VALUE / 2; // Define a high number to represent an impossible situation
4 int n = jobDifficulty.length; // The total number of jobs
5 int[][] dp = new int[n + 1][d + 1]; // Dynamic programming table
6
7 // Initialize all dp table values with MAX_DIFFICULTY, except for the starting point
8 for (int[] row : dp) {
9 Arrays.fill(row, MAX_DIFFICULTY);
10 }
11 dp[0][0] = 0; // Base case: 0 jobs on day 0 has difficulty 0
12
13 // Fill in the dynamic programming table
14 for (int i = 1; i <= n; ++i) { // For each job
15 for (int j = 1; j <= Math.min(d, i); ++j) { // For each day, until the min of current job index and days
16 int maxDifficulty = 0; // To keep track of the maximum difficulty of jobs for the current day
17 // Iterate through the previous jobs to find the minimum difficulty
18 for (int k = i; k > 0; --k) {
19 maxDifficulty = Math.max(maxDifficulty, jobDifficulty[k - 1]); // Find max difficulty among jobs
20 // Update the dp table for the minimum difficulty after completing current job on day j
21 dp[i][j] = Math.min(dp[i][j], dp[k - 1][j - 1] + maxDifficulty);
22 }
23 }
24 }
25 // If the final value is unmodified from the MAX_DIFFICULTY, it means it's not possible to schedule jobs within d days
26 return dp[n][d] >= MAX_DIFFICULTY ? -1 : dp[n][d];
27 }
28}
29
1class Solution {
2public:
3 int minDifficulty(vector<int>& jobDifficulty, int d) {
4 int numJobs = jobDifficulty.size();
5
6 // Create array to store the minimum difficulty on day j having completed job i
7 int minDiff[numJobs + 1][d + 1];
8
9 // Initialize the array with high initial values, except for start state
10 memset(minDiff, 0x3f, sizeof(minDiff));
11 minDiff[0][0] = 0;
12
13 // Iterate through all jobs
14 for (int i = 1; i <= numJobs; ++i) {
15 // For each job, iterate through all possible days, but never more than i days
16 for (int day = 1; day <= min(d, i); ++day) {
17 int maxDifficulty = 0;
18
19 // Looking for the last job on the previous day to minimize today's difficulty
20 for (int k = i; k; --k) {
21 // Update the max difficulty for today's job set (k-1 to i)
22 maxDifficulty = max(maxDifficulty, jobDifficulty[k - 1]);
23
24 // Recurrence relation:
25 // minDiff for job i on day 'day' is the minimum of its current value or
26 // the sum of max difficulty encountered today and
27 // the best we could have done through job k-1 on day 'day-1'
28 minDiff[i][day] = min(minDiff[i][day], minDiff[k - 1][day - 1] + maxDifficulty);
29 }
30 }
31 }
32
33 // Check if it's possible to schedule jobs within d days. If not, return -1
34 return minDiff[numJobs][d] == 0x3f3f3f3f ? -1 : minDiff[numJobs][d];
35 }
36};
37
1function minDifficulty(jobDifficulty: number[], days: number): number {
2 const numOfJobs = jobDifficulty.length; // number of jobs
3 const INF = 1 << 30; // represents an infinite difficulty, used as an initial value
4 const dp: number[][] = new Array(numOfJobs + 1)
5 .fill(0)
6 .map(() => new Array(days + 1).fill(INF)); // initialize the dp array
7 dp[0][0] = 0; // base case: 0 jobs done in 0 days has a difficulty of 0
8
9 // Populate the dp table
10 for (let i = 1; i <= numOfJobs; ++i) {
11 for (let j = 1; j <= Math.min(days, i); ++j) { // Each job can only be scheduled if we have enough days
12 let maxDifficulty = 0; // tracks the maximum difficulty of the current job set
13
14 // Loop to find the minimum difficulty if the current job ends the current day
15 for (let k = i; k > 0; --k) {
16 maxDifficulty = Math.max(maxDifficulty, jobDifficulty[k - 1]);
17 dp[i][j] = Math.min(dp[i][j], dp[k - 1][j - 1] + maxDifficulty);
18 }
19 }
20 }
21
22 // Return the minimum difficulty to complete all jobs in the given days
23 // If it's still INF, it means it's impossible to schedule all jobs, hence return -1
24 return dp[numOfJobs][days] < INF ? dp[numOfJobs][days] : -1;
25}
26
Time and Space Complexity
The time complexity of the provided code is O(n^2 * d)
. This is because there are three nested loops where the outermost loop runs for n
iterations (jobs), the middle loop runs for at most d
iterations (days), and the innermost loop also runs for at most n
iterations, but on average will run fewer times as k
decreases. However, in the worst case, the inner loop still contributes n
operations per iteration of the middle loop. The product of these gives the time complexity of O(n^2 * d)
.
The space complexity of the code is O(n * d)
. This arises from the use of a 2D array f
with dimensions n + 1
by d + 1
. Since the only other variables are constant size integers and not dependent on n
or d
, f
dominates the space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first