Hello, reader 👋🏽 ! Welcome to day 16 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.
Today, I will be picking up LeetCode's daily challenge problem: 1335. Minimum Difficulty of a Job Schedule.
🤔 Problem Statement
Given n jobs and d days, we need to schedule all the jobs such that:
- jobs[i] is only completed after all jobs[j] where
0= <=j < iare completed first. - All the n jobs needs to be scheduled within d days
- At least one job needs to be completed on a given day
- jobs[i] is only completed after all jobs[j] where
Job difficulty on any day is the maximum job difficulty of all jobs completed that day.
- We need to return the minimum sum of all the jobs performed across d days.
- If it's not possible to complete all jobs in d days, we have to return -1.
-E.g.:
- `Input: jobDifficulty = [6,5,4,3,2,1], d = 21 => 7
- [6,5,4,3,2] performed on day 1 and [1] performed on day 2. 6+1 = 7 -E.g.:
Input: jobDifficulty = [1,1,1], d = 4=> -1- It's not possible to complete all jobs in 3 days. On one of the days no jobs will be performed. Hence return -1.
- `Input: jobDifficulty = [6,5,4,3,2,1], d = 21 => 7
💬 Thought Process - Recursion
- Looking at the input, we can see that there can be multiple ways to group jobs on all of the d days.
- So the simplest way is to look at all the possible groups and then find the minimum across the groupings on all days.
- That means, to solve for day = 1, we can split the array at [0,0], [0,1], [0,2],... [0,n-d], And these could further be split in the remaining days.
Some thing like this:
Each of the branches in the above image can further be split into more sub-branches until
day = 1, which is when we will stop, and simply return the maximum of the start index until end of the jobs.In total, this is what the recursion tree will look like:
Basically for every pair of start of the group and the day the group was cut, we are running a recursion.
Let's look into the code now.
👩🏽💻 Solution - Recursion
- Below is the code for recursive solution.
class Solution {
public int minDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.length;
if(d > n) {
return -1;
}
return minDifficultyHelper(jobDifficulty, d, 0, n);
}
//
private int minDifficultyHelper(int[] jobDifficulty, int d, int start, int n) {
if(d == 1) {
// return the max at this value from start to n
return getMax(jobDifficulty, start, n-1);
}
int minValue = Integer.MAX_VALUE;
for(int i = start; i<=n-d; i++) {
// This gets the values at the cut [i+1, n)
int nextCut = minDifficultyHelper(jobDifficulty, d-1, i+1, n);
int currentCutMax = getMax(jobDifficulty, start, i);
minValue = Math.min(minValue, (nextCut + currentCutMax));
}
return minValue;
}
private int getMax(int[] jobDifficulty, int i, int j) {
int currentCutMax = 0;
while(i <= j) {
currentCutMax = Math.max(jobDifficulty[i], currentCutMax);
i++;
}
return currentCutMax;
}
}
Time Complexity: O(n-d!)
- n = number of jobs
- d = number of days
Space Complexity: O(n-d)
- n = number of jobs
- d = number of days
- As you may have suspected after looking at the time complexity, the above code leads to TLE on LeetCode.
- Also, it's a terrible algorithm. So let's optimise this.
💬 Thought Process - 2D Dynamic Programming Memoization
- In the recursion diagram above, we've used the combination of start and day d to break the problem into smaller chunks.
- We can also see that there are multiple overlapping sub problems. Hence, we can use DP to memoize the values that was already computed.
For e.g. the group on day 1 starting from index = 5 on day 1, is an overlapping problem and we can see it across multiple subtrees.
So we will use 2D dynamic programming and memoize values for the pair of
<startIndex, day>.
Let's look into the code for this approach.
👩🏽💻 Solution - 2D Dynamic Programming Memoization
Below is the code for the above approach.
class Solution { public int minDifficulty(int[] jobDifficulty, int d) { int n = jobDifficulty.length; if(d > n) { return -1; } int[][] memo = new int[n+1][d+1]; for(int[] row: memo) { Arrays.fill(row, Integer.MAX_VALUE); } return minDifficultyHelper(jobDifficulty, d, 0, n, memo); } // private int minDifficultyHelper(int[] jobDifficulty, int d, int start, int n, int[][] memo) { if(d == 1) { // return the max at this value from start to n return getMax(jobDifficulty, start, n-1); } if(memo[start][d] != Integer.MAX_VALUE) { return memo[start][d]; } int minValue = memo[start][d]; for(int i = start; i<=n-d; i++) { // This gets the values at the cut [i+1, n) int nextCut = minDifficultyHelper(jobDifficulty, d-1, i+1, n, memo); int currentCutMax = getMax(jobDifficulty, start, i); minValue = Math.min(minValue, (nextCut + currentCutMax)); memo[start][d] = minValue; } return memo[start][d] = minValue; } private int getMax(int[] jobDifficulty, int i, int j) { int currentCutMax = 0; while(i <= j) { currentCutMax = Math.max(jobDifficulty[i], currentCutMax); i++; } return currentCutMax; } }Time Complexity: O(n*d*n) - We are making n*d calls and at each call we are doing n-d amount of work. Space Complexity: O(n*d) + O(n-d) implicit stack space - We are using aux space to memoize values
- You can also improve the time complexity as well as optimise space with tabulation. But, I will not be sharing the solution for those here.
You can find the code for this problem on GitHub repo: 1335. Minimum Difficulty of a Job Schedule.
Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!
Thank you for reading!