Minimum Difficulty of a Job Schedule - Leetcode 1335 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/minimum...
0:00 - Read the problem
0:23 - Drawing Explanation
8:00 - Coding Explanation
leetcode 1335
#neetcode #leetcode #python

[@walkastray007]

Hey Neetcode! I really appreciate the daily leetcode problem videos. They're such a nice way to start my day. It's sort of a ritual for me at this point to attempt a leetcode problem. I actually managed to get the correct thoughts/observations to solve the problem, but actually translating that into code was a bit tricky. As most hard problems are.
Hope to see you tomorrow!

[@MP-ny3ep]

Beautiful explanation as always. Thank you.

[@minaFbeshay]

The best to explain dynamic programming so far! Keep it bro

[@laumatthew71]

Great explanation as usual, thank you sir !

[@aadil4236]

You are doing a really amazing and good work Navdeep. May god gives you everything you want in life. Happy New Year in advance my friend! You are a really amazing teacher! God bless you.

[@tanmaychavan7004]

Thanks a bunch, was waiting for this.

[@yang5843]

Was hoping you would come in clutch today to solve the problem!

[@nahidtanvir5901]

Shouldn't I calculate cur_max before checking cache?

[@SergeKnysh]

Great, all good now - thanks a lot

[@prajjwaldubey5787]

In the interview do I need to do the recursive + caching approach or the tabulation approach for any dp problem ????

[@caleb.39]

Wow today's problem was so much easier than yesterday's lol. yesterday's I had spent 40 minutes trying to think about it before seeing your video. Today's problem I was able to solve it by myself in 20 minutes

[@GameFlife]

fast fix tks NEET!

[@venketeshpanda5183]

And our saviour is here :D

[@Manish-fd5jb]

Just put that DP check condition after calculating cur_max; it makes a big difference.

[@user-od5rd7ss3t]

I am wondering if you can explain the monotonic stack solution as it helps learn everyone new concept. Thank you :)

[@satwiktatikonda764]

if we give this memoization code in a interview will the
interviewer be satisfied or will he ask us to optimize more and write a tabulation code?

[@YashRekha594]

I consider myself very bad at dynamic programming. I need to start from the basic DP. Please suggest where I can start and learn DP.

[@sadiksikder7014]

climbing stairs, target sum, house robber, coin change, lcs

[@csam11100]

Thanks for sharing!
BTW, We can add the following condition in your dfs function to prune the useless states.
remain_tasks = (n - 1) - i + 1
if remain_tasks < d:
return math.inf

[@mahimanzum]

The time complexity analysis is incorrect i believe. It should be O(n*d*max_value_of_array) max value of array and length of the array are different values. Please correct me if i am wrong

[@NeetCodeIO]

Yeah you're right, but I think it would be distinct_vals_in_array

[@yang5843]

@@NeetCodeIO isn't max value a constant

[@hamirmahal]

O(n*d*distinct_vals_in_array) is still O(n*d*n) because there are at most n distinct values in the array.

[@6kostia]

you can get ~150ms for a recursive solution

[@_PixelPioneer_]

Great Explanation but why don't you solve this problem in bottom up approach!

[@caothanhluan1813]

I think memoization is kinda straightforward to solve this question

[@_PixelPioneer_]

@@caothanhluan1813 ya may be u are right ✅

[@shreehari2589]

God damn one heck of a problem this was

[@yang5843]

class Solution {
Map map = new HashMap();
public int minDifficulty(int[] jobDifficulty, int d) {
if ( jobDifficulty.length < d ) return -1;
return dfs(0,jobDifficulty,d,-1);
}
int dfs(int i, int[] jb, int d, int max) {
if ( map.containsKey(i+" "+d+" "+max)) return map.get(i+" "+d+" "+max);
if ( d == 0 && i == jb.length ) return 0;
if ( d == 0 || i == jb.length ) return 10000;

max = Math.max(max,jb[i]);
//take
int min = dfs(i+1,jb,d,max);

//ignore
min = Math.min(min,max + dfs(i+1,jb,d-1,-1));

map.put(i+" "+d+" "+max,min);
return min;

}
}

[@chugisan6847]

Is making a map-key by concatenating values safe? I mean, for i = 23, d = 4, max = 5 and for i = 2, d = 34, max = 5, the map-key would be 2345 in both the cases. I know the chances for this to happen are very slim, but I just wanted to know if this way of making map-keys is standard or it's something that you use for yourself.

[@yang5843]

@@chugisan6847 good question, I'm space separating the integers so that doesn't happen

[@chugisan6847]

@@yang5843 Got you! Thank you for the answer.

[@joydeeprony89]

return 10000 , please share the logic behind magic number 10000 ?

[@yang5843]

@@joydeeprony89 it's an arbitrary large number, if I used max int here, there would be an overflow

[@oijgg3p]

class Solution:
def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
n = len(jobDifficulty)
if n < d:
return -1 # Cannot schedule all jobs in d days
memo = {}
def dp(day, idx):
if (day, idx) in memo:
return memo[(day, idx)]
if day == 1:
# On the last day, we need to finish all remaining jobs, so return the maximum difficulty
memo[(day, idx)] = max(jobDifficulty[idx:])
return memo[(day, idx)]
min_difficulty = float('inf')
max_difficulty = 0
# Iterate backward to find the minimum difficulty
for i in range(idx, n - day + 1):
max_difficulty = max(max_difficulty, jobDifficulty[i])
rest_difficulty = dp(day - 1, i + 1)
min_difficulty = min(min_difficulty, max_difficulty + rest_difficulty)
memo[(day, idx)] = min_difficulty
return min_difficulty
result = dp(d, 0)
return result if result != float('inf') else -1

[@tariqelamin5847]

First comment

[@srirambharadwaj1937]

can anyone help me with this,..why this code doesn't work. as expected
class Solution:
def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
n = len(jobDifficulty)
if n

[@sadiksikder7014]

how are you returning todayCost when you have not define it