Non-Overlapping Intervals - Leetcode 435 - Python

[@raminanushiravani9524]

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

[@Harry-ko6ws]

yeah I think that is what he wanted to say :v I have to pause the video few times here just to verify

[@KannanMavila]

Came here to type the same :) I wish @NeetCode would pin this.

[@riddhabose9653]

exactly, even i was thinking the same

[@bouzie8000]

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.

[@c-mmon2257]

7:39 you have to remove which ends later and not first.

[@ashsheth1482]

thanks for this comment

[@willl5524]

true, it should be keeping the one that ends first. That explains the code "prevEnd = min(end, prevEnd)"

[@junjason4114]

The time should be 7:28

[@murali1790able]

thanks for comment.

[@murali1790able]

@@junjason4114 no time 6:35

[@kaixuanhu8332]

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

[@yyyooohhhooo]

yup i was confused lmao

[@PradiptaGitaya]

Yes. I was confused as well

[@dingusagar]

Thank God there are comments!😅

[@ravig5413]

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!.

[@NeetCode]

Thanks! Happy to help :)

[@karthikkrishna8124]

whre can i get the excel sheet?

[@jonnatanortiz7159]

You literally give me hope when it comes to getting better at algorithms 🙏🏼

[@johns3641]

So happy every time I see a LC 75 problem explained. Thank you!

[@hwang1607]

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

[@deadsippy]

thank you neetcode

[@JulianBoilen]

7:33 "we want to remove the one that ends first" **crosses out one the ends last** 😕

[@PradiptaGitaya]

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]

[@Moch117]

@@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

[@NinjaN0ob]

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

[@mirceskiandrej]

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???

[@BorisIsASpider]

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

[@rnelert]

He just made a mistake and said a different thing that he meant.

[@sentinel-y8l]

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:].

[@jeffwei]

Thanks, I was trying to figure out what the benefit to sorting by end was

[@MistaT44]

literally the best explanations on youtube! so clear and concise.

[@JaredDunn-r9c]

This is such an amazing explanation. I can't thank you enough for all that you've done for us students.

[@jonaskhanwald566]

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.

[@rajiththennakoon7392]

Dude I love martha 😍

[@jonaskhanwald566]

@@rajiththennakoon7392 I too. But not in last season.

[@AK-kq1mk]

322k

[@xinyuwang7477]

I find sorting by the end time is easier. If there's overlap, just counter + 1 without other processing.

[@azamatik3]

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

[@stith_pragya]

Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@saketkumar9392]

Great Explanation as always, thanks man.

[@anupamkolay193]

What an explanation! You make it look so easy. Thank you.

[@arifrubayet8715]

Neet! Why your voice is so satisfying bro? You r Great Man!!🤝

[@amansingh.h716]

ohh i was thinking about removing part but we just need to update the last value which is smaller between previous and current interval

[@deepakreddy6528]

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

[@ChanChan-pg4wu]

Very crisp explanation and pretty smart!

[@haniehh2160]

Great Explanation!!! Where can I find the spreadsheet you showed at the beginning of the video?

[@YawarMurtaza-z9k]

Would it be simpler if we count non-overlapping events then subtract those from total events?

[@dinosauraesthetic]

Can we think of it in a dynamic programming way?

[@jaskaransingh0304]

Great explanation

[@mrshodz]

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)?

[@jayshekarharkar8119]

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.

[@ancai5498]

I think the logic should always remove the one end last, so it should have less chance of overlapping with the next interval.

[@danielsun716]

@Neetcode, can you introduce the DP solution? Thanks

[@blade99x]

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

[@treyamrich6096]

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.

[@shantanusingh3334]

what will be the code if I need to remove those overlapping intervals and print the remaining list?

[@anandkumar72]

best explanation

[@lxu5148]

I wonder if it's feasible for you to do 1235. Maximum Profit in Job Scheduling, as well.

[@AnkitaNallana]

THANK YOU FOR SORTING IT BY THE START TIMES!

[@MIDNightPT4]

Amazing explanation as always

[@xuzack832]

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"?

[@rajiththennakoon7392]

What is the device/software are you using for drawing?

[@NeetCode]

I just use a gaming mouse, with Paint3D

[@coolmangame4141]

how are you so good with drawing with mouse? many people would love to do that lol

[@fawadaliq]

Wow. I can't event write this good with a drawing tablet.

[@rohitheshwarwak5720]

On an interview is it reasonable to expect an interviewer to ask for a semi-formal proof?

[@supercarpro]

bro ur a fucking legend

[@AmolGautam]

Thank you.

[@adithyasn6315]

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 !!!!

[@tejasnakhate]

This problem comes under label of dynamic programming. I wonder why?

[@abhinay4200]

got me confused as well

[@thehdchan]

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.

[@VivekMishrathetraveller]

Nice, can you also upload a video of critical connection LC 1192

[@garitina987]

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!

[@giridharjadala2182]

Did anyone try doing this problem using Kruskal's algorithm ,maybe it might work ,give it go.

[@VikasGupta-ok9lh]

Understood

[@ChazWinter]

You keep saying "remove the one that ends first" when you mean "keep the one that ends first"

[@bchen1403]

smooth

[@osamaayman3765]

Thankss

[@mruduladdipalli5417]

I came up with same solution without watching this video, remembered your previous video where sorting was done on start value

[@ryan-bo2xi]

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

[@edwardteach2]

U a God

[@lubeckable]

Idk but this solution doesn't work with java idk why

[@cosmicheathen1955]

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; }