your explanation are always great. Just one thing I noticed you said at 7:30, "removing the one that ends first", I think you meant keeping the one that ends first
The way this video took me an hour to undestand because of this mistake lol. Would have saved a lot of time if I had just continued watching to see he obviously made a mistake instead of pausing lol.
Are you the nicest person!! Neet. Thanks bud! for compiling/sharing the above lists and sharing the excel with the notes. All in 1 place. Awesome!! Be good!.
I think he means to remove the one that ends later... If we remove the ends first, there are still possibilities other intervals may overlap.. Like: [1,5], [3,10], [7,12] First it will overlap on [1,5] and [3,10]. If we remove [1,5] unfortunately we will have another overlap on [3,10] with [7,12] But that's not the case if we remove [3,10]
came up with this after someone said to sort by the ends, may be more intuitive class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: intervals.sort(key = lambda x : x[1]) cur = intervals[0] res = 0 for i in range(1, len(intervals)): if intervals[i][0] < cur[1]: res += 1 else: cur = intervals[i] return res
If you sort the intervals by increasing period ends, then you don't need the min(end, prevEnd) inside the loop. You can also initialize prevEnd to -inf and iterate over the entire list instead of [1:].
Wait, if we want to minimize the chance that an interval overlaps with the next one, don't we want to remove the longer one. The longer the interval is, the higher the chance it overlaps with something. Why did he say then that "of course we want to remove the shorter one" at 6:40???
In the example right after 6:40 he explains why u don't always want to remove the longest interval. A shorter interval can still cause multiple deletions
Hey Neet, I noticed you keep saying "remove the one that ends first" when you are not pointing to the one that ends first. I believe you meant "keep the one that ends first"?
Why is the time complexity the complexity of the sort algorithm? I would assume it would be the time complexity equal to the O(sort algorithm) + O(algorithm to removed overlapping ranges)?
Because O(algorithm to removed overlapping range) (O(n) ie. linear in time) is negligible compared to O(sort algorithm) (O(nlogn)) could & should be ignored.
i got to the same solution except I was trying to remove the interval that had the bigger gap but it was failing. Once I made a small change to comparing the endpoints instead it worked. Could someone tell me why removing simply removing the bigger one doesnt work? Thanks
A larger interval does have a greater chance of overlapping with more intervals. However, it's countered by one case. Let's say the left interval has a size of 12 and overlaps with 1 interval (the right interval it's being compared with). The right interval has a size of 8 and overlaps with 3 intervals. In this case, removing the left interval would be wrong because the right interval still overlaps with 3 intervals. The logic is flawed. The greedy choice to remove the interval that ends the latest always works because that interval has a higher or equal chance of overlapping with more intervals in the future.
If anyone needs a simpler and more straightforward code, see if this helps: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: intervals = sorted(intervals, key = lambda x : x[0]) res = 0 for i in range(1, len(intervals)): if intervals[i][0] < intervals[i-1][1]: res += 1 intervals[i][1] = min(intervals[i-1][1], intervals[i][1]) return res
Dynamic programming is defined by finding the optimal solution to a subset of problems in order to solve the larger problem. Because it is using a greedy method algorithm, it's a dynamic programming problem.
This is the code for sorting based on second element on the list. this is slightly taking more time (measured based on custom timer method in my local ). I think because of lambda to run while sorting. But this looks simple code. class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: res = 0 intervals = sorted(intervals, key=lambda i: i[1]) ele = intervals[0][1] for i in range(len(intervals)-1): if ele > intervals[i+1][0]: res+=1 else: ele = intervals[i+1][1] return res Happy Coding !!!!
Big fan of your stuff Neet, but if I had a suggestion, I wish you would do a much better job with catering to people who aren't solving these in python. For example, I'm doing C++ and didn't understand what the "start,end" was supposed to mean in the loop and had to do some digging to figure it out. :) Just a suggestion and hoping you can take it into consideration for the future. Regardless, you're videos are a god send!
how about this simple code def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: ans = 0 currentEnd = -math.inf for interval in sorted(intervals, key=lambda x: x[1]): if interval[0] >= currentEnd: currentEnd = interval[1] else: ans += 1 return ans
your explanation are always great. Just one thing I noticed you said at 7:30, "removing the one that ends first", I think you meant keeping the one that ends first
yeah I think that is what he wanted to say :v I have to pause the video few times here just to verify
Came here to type the same :) I wish @NeetCode would pin this.
exactly, even i was thinking the same
The way this video took me an hour to undestand because of this mistake lol. Would have saved a lot of time if I had just continued watching to see he obviously made a mistake instead of pausing lol.
7:39 you have to remove which ends later and not first.
thanks for this comment
true, it should be keeping the one that ends first. That explains the code "prevEnd = min(end, prevEnd)"
The time should be 7:28
thanks for comment.
@@junjason4114 no time 6:35
you mean remove the interval which ends later right? not ends first, it is the greedy approach in order to avoid the later potentials overlapping
yup i was confused lmao
Yes. I was confused as well
Thank God there are comments!😅
Are you the nicest person!! Neet. Thanks bud! for compiling/sharing the above lists and sharing the excel with the notes. All in 1 place. Awesome!! Be good!.
Thanks! Happy to help :)
whre can i get the excel sheet?
@@karthikkrishna8124 it's in the video description
So happy every time I see a LC 75 problem explained. Thank you!
You literally give me hope when it comes to getting better at algorithms 🙏🏼
7:33 "we want to remove the one that ends first" **crosses out one the ends last** 😕
I think he means to remove the one that ends later...
If we remove the ends first, there are still possibilities other intervals may overlap..
Like: [1,5], [3,10], [7,12]
First it will overlap on [1,5] and [3,10]. If we remove [1,5] unfortunately we will have another overlap on [3,10] with [7,12]
But that's not the case if we remove [3,10]
@@PradiptaGitaya Yeah I think so too. That part was confusing me because I thought it made more sense to remove the one that ends later
thank you neetcode
came up with this after someone said to sort by the ends, may be more intuitive
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key = lambda x : x[1])
cur = intervals[0]
res = 0
for i in range(1, len(intervals)):
if intervals[i][0] < cur[1]:
res += 1
else:
cur = intervals[i]
return res
Nice one. I'm a subscriber of Neetcode since it had less than 2k subscribers. Now its 31K. All the best to reach 100K soon.
Dude I love martha 😍
@@rajiththennakoon7392 I too. But not in last season.
322k
literally the best explanations on youtube! so clear and concise.
This is such an amazing explanation. I can't thank you enough for all that you've done for us students.
it is absolutely disgusting how your able to break down the problem and codify it so well, thank you so much I have learned so much from your videos
If you sort the intervals by increasing period ends, then you don't need the min(end, prevEnd) inside the loop. You can also initialize prevEnd to -inf and iterate over the entire list instead of [1:].
Thanks, I was trying to figure out what the benefit to sorting by end was
What an explanation! You make it look so easy. Thank you.
Wait, if we want to minimize the chance that an interval overlaps with the next one, don't we want to remove the longer one. The longer the interval is, the higher the chance it overlaps with something. Why did he say then that "of course we want to remove the shorter one" at 6:40???
In the example right after 6:40 he explains why u don't always want to remove the longest interval. A shorter interval can still cause multiple deletions
He just made a mistake and said a different thing that he meant.
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I find sorting by the end time is easier. If there's overlap, just counter + 1 without other processing.
Great Explanation as always, thanks man.
thank u so much! When i saw this problem, I had no idea how to even get close to this problem, let alone a solution
Very crisp explanation and pretty smart!
Great Explanation!!! Where can I find the spreadsheet you showed at the beginning of the video?
ohh i was thinking about removing part but we just need to update the last value which is smaller between previous and current interval
Can we think of it in a dynamic programming way?
Neet! Why your voice is so satisfying bro? You r Great Man!!🤝
Would it be simpler if we count non-overlapping events then subtract those from total events?
Great explanation
best explanation
Hey Neet, I noticed you keep saying "remove the one that ends first" when you are not pointing to the one that ends first. I believe you meant "keep the one that ends first"?
@Neetcode, can you introduce the DP solution? Thanks
what will be the code if I need to remove those overlapping intervals and print the remaining list?
What is the device/software are you using for drawing?
I just use a gaming mouse, with Paint3D
how are you so good with drawing with mouse? many people would love to do that lol
Wow. I can't event write this good with a drawing tablet.
On an interview is it reasonable to expect an interviewer to ask for a semi-formal proof?
Why is the time complexity the complexity of the sort algorithm? I would assume it would be the time complexity equal to the O(sort algorithm) + O(algorithm to removed overlapping ranges)?
Because O(algorithm to removed overlapping range) (O(n) ie. linear in time) is negligible compared to O(sort algorithm) (O(nlogn)) could & should be ignored.
I wonder if it's feasible for you to do 1235. Maximum Profit in Job Scheduling, as well.
Thank you.
i got to the same solution except I was trying to remove the interval that had the bigger gap but it was failing. Once I made a small change to comparing the endpoints instead it worked. Could someone tell me why removing simply removing the bigger one doesnt work? Thanks
A larger interval does have a greater chance of overlapping with more intervals. However, it's countered by one case. Let's say the left interval has a size of 12 and overlaps with 1 interval (the right interval it's being compared with). The right interval has a size of 8 and overlaps with 3 intervals. In this case, removing the left interval would be wrong because the right interval still overlaps with 3 intervals. The logic is flawed. The greedy choice to remove the interval that ends the latest always works because that interval has a higher or equal chance of overlapping with more intervals in the future.
If anyone needs a simpler and more straightforward code, see if this helps:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals = sorted(intervals, key = lambda x : x[0])
res = 0
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]:
res += 1
intervals[i][1] = min(intervals[i-1][1], intervals[i][1])
return res
I think the logic should always remove the one end last, so it should have less chance of overlapping with the next interval.
Nice, can you also upload a video of critical connection LC 1192
This problem comes under label of dynamic programming. I wonder why?
got me confused as well
Dynamic programming is defined by finding the optimal solution to a subset of problems in order to solve the larger problem. Because it is using a greedy method algorithm, it's a dynamic programming problem.
Amazing explanation as always
bro ur a fucking legend
THANK YOU FOR SORTING IT BY THE START TIMES!
This is the code for sorting based on second element on the list. this is slightly taking more time (measured based on custom timer method in my local ). I think because of lambda to run while sorting. But this looks simple code.
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
res = 0
intervals = sorted(intervals, key=lambda i: i[1])
ele = intervals[0][1]
for i in range(len(intervals)-1):
if ele > intervals[i+1][0]:
res+=1
else:
ele = intervals[i+1][1]
return res
Happy Coding !!!!
Thankss
Big fan of your stuff Neet, but if I had a suggestion, I wish you would do a much better job with catering to people who aren't solving these in python. For example, I'm doing C++ and didn't understand what the "start,end" was supposed to mean in the loop and had to do some digging to figure it out. :) Just a suggestion and hoping you can take it into consideration for the future. Regardless, you're videos are a god send!
Understood
You keep saying "remove the one that ends first" when you mean "keep the one that ends first"
Did anyone try doing this problem using Kruskal's algorithm ,maybe it might work ,give it go.
smooth
I came up with same solution without watching this video, remembered your previous video where sorting was done on start value
how about this simple code
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
ans = 0
currentEnd = -math.inf
for interval in sorted(intervals, key=lambda x: x[1]):
if interval[0] >= currentEnd:
currentEnd = interval[1]
else:
ans += 1
return ans
U a God
Idk but this solution doesn't work with java idk why
worked for me:
public int eraseOverlapIntervals(int[][] intervals) {
List res = new ArrayList();
Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // sorting according to start
int prevEnd = intervals[0][1];
int count=0;
for(int i =1; i start ){
prevEnd = Math.min(prevEnd,end);
count++;
}
else{
prevEnd =end;
}
}
return count;
}