Maximum Profit in Job Scheduling - Leetcode 1235 - Python
Vložit
- čas přidán 23. 07. 2024
- 🚀 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
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 !
Thank you for this video, I've recently started doing Leetcode dailies and through your videos I really understood the problems :)
Neetcode please keep uploading videos this helps alot thank you so much❤
Excellent work! Thank you for your explaination!
Thank you Navdeep so much for these daily videos.
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 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?
Great explanation
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!
You are my glorious king NeetCode I love you
Thanks for this video
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
Best explanation EVER in this entire history of DP
Why you have used -1, -1 in the binary search tuple, how is that working, can you please explain.
@neetcode Why do you so cache dict instead of @cache ?
Please upload videos of leetcode contests too
I coudnt understand this one , can you please tell me all the prerequisites for this one
i too need the prerequisites, can somebody help?
@@ShyGuy_16 backtracking
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 ❤
your explanation is too good
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!
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 ????
I did like that do sort and then binary search
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.
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?
May you please link the documentation where you read this from?
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?
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])
What would the binary search code look like if we implemented it ourselves?
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] < val:
left = mid + 1
return left
So you can change it in the solution: j = self.search_right_index(schedule, schedule[i][1])
same question
why aren't editorial are opening?
can someone explain why the recursion is n^2 and not 2^n?
before caching the runtime was 2^n, after caching it became n^2
How do I get the intuition? I understand the logic, but I cant help build up logic without watching your video? Please help sensei.
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!
Oof a hard one
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
Doing this in c++ is like 10x harder...
I'll try to put my answer if I finished it.
Bro just do it in python
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
@@civilizedmonster yeah got my mistake thanks bro
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
u need to sort to check for overlap its a greedy activity selection problem
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 < s.length && s[j][0] < s[i][1] )
j++;
max = Math.max(next,s[i][2] + dfs(j));
map.put(i,max);
return max;
}
}