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!.
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 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
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:].
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]
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 !!!!
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
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.
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.
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.
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
7:39 you have to remove which ends later and not first.
Yeah I think he misspoke, you want to remove the one that ends later so that there's less chance of overlapping in the future I believe
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.
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.
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?
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!😅
So happy every time I see a LC 75 problem explained. Thank you!
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
You literally give me hope when it comes to getting better at algorithms 🙏🏼
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
literally the best explanations on youtube! so clear and concise.
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
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
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
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
This is such an amazing explanation. I can't thank you enough for all that you've done for us students.
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 !!!!
I find sorting by the end time is easier. If there's overlap, just counter + 1 without other processing.
THANK YOU FOR SORTING IT BY THE START TIMES!
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.
What an explanation! You make it look so easy. Thank you.
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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!
ohh i was thinking about removing part but we just need to update the last value which is smaller between previous and current interval
Would it be simpler if we count non-overlapping events then subtract those from total events?
Neet! Why your voice is so satisfying bro? You r Great Man!!🤝
Great explanation
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.
Great Explanation!!! Where can I find the spreadsheet you showed at the beginning of the video?
I think the logic should always remove the one end last, so it should have less chance of overlapping with the next interval.
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"?
I wonder if it's feasible for you to do 1235. Maximum Profit in Job Scheduling, as well.
Thank you.
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.
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.
what will be the code if I need to remove those overlapping intervals and print the remaining list?
Amazing explanation as always
Nice, can you also upload a video of critical connection LC 1192
bro ur a fucking legend
@Neetcode, can you introduce the DP solution? Thanks
Did anyone try doing this problem using Kruskal's algorithm ,maybe it might work ,give it go.
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
Thankss
You keep saying "remove the one that ends first" when you mean "keep the one that ends first"
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.
Understood
U a God
smooth
I came up with same solution without watching this video, remembered your previous video where sorting was done on start value
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;
}