Maximum Profit in Job Scheduling - Leetcode 1235 - 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/maximum...
0:00 - Read the problem
0:57 - Drawing Explanation
7:57 - Coding Explanation
leetcode 1235
#neetcode #leetcode #python
Пікірлер: 55
Great explanation as always. Thank you for going through different methods in the beginning of the video and explaining why you would or wouldn't consider them. That really helps a lot and that's what sets you apart from other youtubers !
Neetcode please keep uploading videos this helps alot thank you so much❤
Thank you for this video, I've recently started doing Leetcode dailies and through your videos I really understood the problems :)
Excellent work! Thank you for your explaination!
Thanks for the video. It would be great if you can also show step by step progress by printing out values because for beginners, it is easier to understand.
Thank you Navdeep so much for these daily videos.
thank you so much ! may god always bless you with happiness n prosperity. you hv taught me a lot, thaanksss from the bottom ofmy heart. please never stop making these videos of the daily challenges.
awesome explanation man!
pls help for take condition cant we just do profit[i] + helper(endTime[i]) cuz we cant start a new process until the current one is finished?
Ok neetcode , love your videos . By the way is it necessary to write the tabulation solution also in interview. We can obviously convert this solution into tabulation but the thing is that recursive solution is intutive but tabulation solution is not. So what i generally do is write recursive solution and then memoize it and then tabulate it
Great explanation
Why you have used -1, -1 in the binary search tuple, how is that working, can you please explain.
Hey neetcode, I want to say thank you. Currently I’m in the final round for both Meta and Amazon for swe internships and your videos and website have been so helpful! I’ve been watching you for the last year and your ability to explain complicated concepts in a simple way has made me much more confident in my computer science abilities, thank you!
Best explanation EVER in this entire history of DP
@neetcode Why do you so cache dict instead of @cache ?
You are my glorious king NeetCode I love you
Thanks for this video
Please upload videos of leetcode contests too
I actually struggled to understand your solution, but then I remembered that the task is to only find the output max value, not the path itself 😂 And then it all clicked, thanks as always. You are up there among the greats such as Abdul Bari ❤
I coudnt understand this one , can you please tell me all the prerequisites for this one
@ShyGuy_16
6 ай бұрын
i too need the prerequisites, can somebody help?
@Kan-JenLiu
6 ай бұрын
@@ShyGuy_16 backtracking
why we can't sort it on the basis of end time, because if we sort with endtime then the minimum endtime will be in ascending order will that not work ????
@saagerbabung5652
6 ай бұрын
I did like that do sort and then binary search
your explanation is too good
@tasneemayham974
6 ай бұрын
Yes, he's the best! Although I code in java, his explanation is so clear that I understand the code in python and can recode it by myself in java!! Amazing!
Great video as always sir. I have learned a lot from your videos and these videos have always motivated me to go for solving problems cause I know there is someone for my help. For this video I have a question that is there a way to solve this problem by sorting the endTime values and if not then why ? I am asking this question because often time I have this confusion that whether I should sort by ending times or starting times. Again thanks a lot for your explainations.
What would the binary search code look like if we implemented it ourselves?
@ianalexthompson
6 ай бұрын
Like this: def search_right_index( self, arr: list[tuple[int, int, int]], val: int ): left, right = 0, len(arr) - 1 while left = val: right = mid - 1 if arr[mid][0] left = mid + 1 return left So you can change it in the solution: j = self.search_right_index(schedule, schedule[i][1])
@KhyatiSatija
6 ай бұрын
same question
why aren't editorial are opening?
can someone explain why the recursion is n^2 and not 2^n?
@jasondubon
2 ай бұрын
before caching the runtime was 2^n, after caching it became n^2
In NeetCode's video, he used: j = bisect.bisect(intervals, (intervals[i][1], -1, -1)) to efficiently get the next index. My questions is this: Python's documentation says that the returned index is > than all indices to its left. That would mean that the start time of j would be > end time of i. But in the problem definition, >= is allowed. What am I missing here?
@tasneemayham974
6 ай бұрын
May you please link the documentation where you read this from?
@user-nj8lu8ld9e
5 ай бұрын
and is it because for [(1, 3, 50), (2, 4, 10), (3, 5, 40), (3, 6, 70)], we are inserting (3, -1, -1), which corresponds to the end time for (1, 3, 50) between (3, 5, 40) and (3, 6, 70) because 40 < 50 < 70?
@GurnurW
2 ай бұрын
According to this video logic, he is comparing one complete tuple (e.g.: end, -1, -1) with the current tuple. Since -1 is smaller than any valid profit or end time, the tuple (end, -1, -1) will fit into the correct position considering the list is sorted by start times. So, it would give the next index whose start time is >= end time of current. If you just want to compare the start times out of the tuple, you can use bisect_left as bisect.bisect_left(intervals, intervals[i][1], key= lambda x: x[0])
How do I get the intuition? I understand the logic, but I cant help build up logic without watching your video? Please help sensei.
@tasneemayham974
6 ай бұрын
Just keep practicing, bro! The more you practice the more similar problems you encounter and you'll eventually become a pro! Remember there are endless LeetCode problems but only a couple of algorithms! Practice makes perfect!
bro i done my code in c++ as class Solution { public: int recur(int i,vector &v,vector &dp){ if(i >= v.size()) return 0; if(dp[i] != -1) return dp[i]; int ans = INT_MIN; // dont include dp[i] = recur(i+1,v,dp); ans = max(ans,dp[i]); // include auto it = lower_bound(v.begin()+i,v.end(),vector{v[i][1],-1,-1}); if(it != v.end()){ int ind = it - v.begin(); dp[i] = max(dp[i],v[i][2] + recur(ind,v,dp)); } ans = max(ans,dp[i]); return ans; } int jobScheduling(vector& startTime, vector& endTime, vector& profit) { int n = endTime.size(); vector v; for(int i=0;i
@Dancedfsk8
6 ай бұрын
Doing this in c++ is like 10x harder... I'll try to put my answer if I finished it.
@shreehari2589
6 ай бұрын
Bro just do it in python
@civilizedmonster
6 ай бұрын
Here you go: class Solution { public: int jobScheduling(vector& startTime, vector& endTime, vector& profit) { vector jobs; int n=startTime.size(); for(int i=0; i
@karthikkongara2265
6 ай бұрын
@@civilizedmonster yeah got my mistake thanks bro
Oof a hard one
this is literally a greedy problem
my stupid brain cant handle this problem.
why it will not work if i don't sort it,and just memoize with maxEndTime,index? i could't able to figure out the why
@kathirchidhambarapandy929
6 ай бұрын
u need to sort to check for overlap its a greedy activity selection problem
@user-gs7xf6qt4l
6 ай бұрын
Since that is not optimal substructure for dp. An anology would be you need to calculate all parent nodes before calculating dp[this] in topological sort.
class Solution { int max = 0; int[][] s; Map map = new HashMap(); public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { s = new int[startTime.length][3]; for (int i=0;ia[0]-b[0]); dfs(0); return max; } int dfs(int i) { if ( i == s.length ) return 0; if ( map.containsKey(i) ) return map.get(i); int next = dfs(i+1); int j = i; while ( j j++; max = Math.max(next,s[i][2] + dfs(j)); map.put(i,max); return max; } }