Non-Overlapping Intervals - Leetcode 435

Non-Overlapping Intervals - Leetcode 435 - Python

Рет қаралды 97,571

Күн бұрын

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
✔️ SPREADSHEET BLIND-75: docs.google.com/spreadsheets/...
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: neetcode.io/problems/non-over...
0:00 - Read the problem
2:22 - Drawing Explanation
9:58 - Coding Explanation
leetcode 435
This question was identified as a microsoft interview question from here: github.com/xizhengszhang/Leet...
#microsoft #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

Пікірлер: 86

@raminanushiravani9524 11 ай бұрын

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 10 ай бұрын

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

@KannanMavila 7 ай бұрын

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

@riddhabose9653 7 ай бұрын

exactly, even i was thinking the same

@bouzie8000 4 ай бұрын

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 2 жыл бұрын

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

@rrjack12345 2 жыл бұрын

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

@ashsheth1482 2 жыл бұрын

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.

@kaixuanhu8332 2 жыл бұрын

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 2 жыл бұрын

yup i was confused lmao

@PradiptaGitaya 2 жыл бұрын

Yes. I was confused as well

@dingusagar 26 күн бұрын

Thank God there are comments!😅

@ravig5413 2 жыл бұрын

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 2 жыл бұрын

Thanks! Happy to help :)

@johns3641 2 жыл бұрын

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

@JulianBoilen 2 жыл бұрын

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

@PradiptaGitaya 2 жыл бұрын

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 11 ай бұрын

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

@jonnatanortiz7159 Жыл бұрын

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

@user-sn9xj5hv8w 10 ай бұрын

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

@MistaT44 2 жыл бұрын

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

@hwang1607 2 ай бұрын

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

@anupamkolay193 Жыл бұрын

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

@ChanChan-pg4wu 2 жыл бұрын

Very crisp explanation and pretty smart!

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

@jonaskhanwald566 2 жыл бұрын

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 2 жыл бұрын

Dude I love martha 😍

@jonaskhanwald566 2 жыл бұрын

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

@AK-kq1mk Жыл бұрын

322k

@NinjaN0ob 2 жыл бұрын

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

@haniehh2160 Жыл бұрын

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

@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

@deepakreddy6528 9 ай бұрын

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

@andrepinto7895 2 жыл бұрын

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

@xinyuwang7477 Жыл бұрын

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

@stith_pragya 8 ай бұрын

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

@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

@AnkitaNallana 4 күн бұрын

THANK YOU FOR SORTING IT BY THE START TIMES!

@arifrubayet8715 2 жыл бұрын

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

@jaskaransingh0304 Жыл бұрын

Great explanation

@mirceskiandrej 2 жыл бұрын

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 2 жыл бұрын

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.

@shantanusingh3334 2 жыл бұрын

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

@VivekMishrathetraveller 2 жыл бұрын

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

@MIDNightPT4 2 жыл бұрын

Amazing explanation as always

@danielsun716 Жыл бұрын

@Neetcode, can you introduce the DP solution? Thanks

@lxu5148 2 жыл бұрын

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

@AmolGautam 5 ай бұрын

Thank you.

@user-xv8ru8ny2v Ай бұрын

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

@seankoo4651 2 жыл бұрын

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.

@supercarpro 2 жыл бұрын

bro ur a fucking legend

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

@rajiththennakoon7392 2 жыл бұрын

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

@NeetCode 2 жыл бұрын

I just use a gaming mouse, with Paint3D

@coolmangame4141 2 жыл бұрын

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

@fawadaliq 2 жыл бұрын

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

@bchen1403 2 жыл бұрын

smooth

@VikasGupta-ok9lh Жыл бұрын

Understood

@osamaayman3765 11 ай бұрын

Thankss

@tejasnakhate 2 жыл бұрын

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

@abhinay4200 2 жыл бұрын

got me confused as well

@thehdchan 2 жыл бұрын

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.

@ancai5498 8 ай бұрын

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

@giridharjadala2182 2 жыл бұрын

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

@xuzack832 10 ай бұрын

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

@edwardteach2 2 жыл бұрын

U a God

@ryan-bo2xi 9 ай бұрын

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

@lubeckable 2 жыл бұрын

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

@cosmicheathen1955 2 жыл бұрын

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

@mruduladdipalli5417 Жыл бұрын

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

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