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 !
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!
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.
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
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 ❤
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?
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])
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 ????
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!
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.
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])
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
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
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.
![[Full Episode] The Restaurant War Thailand ศึกพ่อค้าซ่าแม่ค้าแซ่บ Episode 4 | 13 ต.ค. 67](http://i.ytimg.com/vi/h8N9tY46P-M/mqdefault.jpg)
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 !
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!
So you joined Meta? Can't find you in Amazon internal portal
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 :)
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.
Excellent work! Thank you for your explaination!
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
Why you have used -1, -1 in the binary search tuple, how is that working, can you please explain.
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 ❤
You are my glorious king NeetCode I love you
Best explanation EVER in this entire history of DP
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])
awesome explanation man!
Thanks for this video
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
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
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!
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?
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!
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.
Please upload videos of leetcode contests too
@neetcode Why do you so cache dict instead of @cache ?
Great explanation
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
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
my stupid brain cant handle this problem.
Oof a hard one
this is literally a greedy problem
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;
}
}
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.