Non overlapping intervals

Non overlapping intervals | Leetcode

Рет қаралды 35,457

3 жыл бұрын

This video explains the problem of non-overlapping intervals.This problem is based on greedy algorithm.In this problem, we are required to find the minimum number of intervals which we can remove so that the remaining intervals become non overlapping.I have shown all the 3 cases required to solve this problem by using examples.I have also shown the dry run of this algorithm.I have explained the code walk-through at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL VIDEOS:-
Interval List Intersections: • Interval List Intersec...

Пікірлер: 74

@amalsalim88 3 жыл бұрын

so this is maybe the fourth or fifth time im stumbling upon tech does solution and your videos are really good. you focus on explaining the algorithm. thanks so much for making my life easier

@techdose4u 3 жыл бұрын

Welcome :)

@shaleen0mishra 2 жыл бұрын

Could not get my head around this problem/solution even after referencing multiple 'good' resources. This helped a lot. Great job explaining!

@justshanky3012 2 жыл бұрын

Thank you so much. This looked like a very complicated problem at first. You made it so much simpler

@adityaojha2701 3 жыл бұрын

Thanks Tech Dose once again!! Keep posting questions like this.

@techdose4u 3 жыл бұрын

👍🏼

@vcfirefox 2 жыл бұрын

please keep doing this for many problems. it is VERY hard to find someone explaining the thought process instead of just writing some code on the videos. keep up the excellent work and I wish you the best of luck

@techdose4u 2 жыл бұрын

Thanks 😊

@yjj410 3 жыл бұрын

This is similar to problem where arrival/start and departure/end times are given and we have to give maxim number of guests or trains or events that can happen without collision.

@techdose4u 3 жыл бұрын

Seems the same.

@shubhamrathi3734 2 жыл бұрын

I dont see how. In the problem where arrival/start and departure/end times are given and we have to give maximum number of platforms, we dont care about the start time or the end time. In this problem, we very much care about the start times and the end times.

@johncenakiwi 2 жыл бұрын

Amazing explanation. Coded it with ease. Thank you !

@techdose4u 2 жыл бұрын

Welcome 😊

@user-oy4kf5wr8l 4 ай бұрын

thank you soooooo much. after working at MS for 2 years, i restart my job hunting journey lol.

@K_EC_AushoRoup 3 жыл бұрын

16/18 test cases passed. I am here because of the remaining test cases. Update: And @<a href="#" class="seekto" data-time="445">7:25</a> I got my mistake, I was ignoring or leaving the case when one interval will lie completely inside of the other interval. For example, [2,3] is completely inside the [1,4]. And when I handle those case, 18/18 test cases passed. Thanks, sir for such a diagrammatical explanation.

@techdose4u 3 жыл бұрын

Welcome :)

@paragroy5359 2 ай бұрын

Thanks a lot for making such videos. Great Content

@alltechsimplified2134 Жыл бұрын

amazing explanation as always

@deepanshjohri3997 4 ай бұрын

Thanks alot sir, I stopped the video at <a href="#" class="seekto" data-time="707">11:47</a> and implement the whole code by myself 🙏🙏

@imranimmu4714 11 ай бұрын

Couldnt have found bettter explanation. Thank you.

@pryansh_ 8 ай бұрын

No offence madarsa boy but it should have been "couldn't". There is a spelling error too. Ask from them.

@kaushaljalan2928 3 жыл бұрын

Great effort put up for such an awesome explanation.

@techdose4u 3 жыл бұрын

Thanks :)

@krishnakantsharma6161 3 жыл бұрын

wow you r awesome u explain each and every corner 👏👏 keep it up i m watching all ur videos

@techdose4u 3 жыл бұрын

Thanks

@codelite700 Жыл бұрын

Wow, this was much more intuitive.

@ayushprakash8343 3 жыл бұрын

@TECH DOSE you doing a great job! btw very clear and nice explanation as always :) Cheers!

@techdose4u 3 жыл бұрын

Thanks

@shayestaparveen315 2 жыл бұрын

Thanks!

@ekengineer9868 Жыл бұрын

Awesome Explanatoin

@nitishprasadkushwaha 2 жыл бұрын

u are the saviour

@pranavsharma7479 2 жыл бұрын

all intervals problems are solved by this template thanks a ton

@rakeshsahni_ 3 жыл бұрын

Before it I am frustrated but now I fill better Thanks sir

@techdose4u 3 жыл бұрын

Welcome :)

@prasad.patil12 3 жыл бұрын

Simple and clear explanation 👍

@techdose4u 3 жыл бұрын

Thanks :)

@hardiksardhara3355 3 жыл бұрын

Great explanation

@techdose4u 3 жыл бұрын

Thanks

@InvincibleMan99 2 жыл бұрын

Thanks

@joshithmurthy6209 Жыл бұрын

thanks

@therealaspirant1882 3 жыл бұрын

awesome explination bro

@techdose4u 3 жыл бұрын

Thanks

@Voice_Of_Thoughts 3 жыл бұрын

Nice explanation

@techdose4u 3 жыл бұрын

Thanks

@girikgarg8 Жыл бұрын

In overalapping case 2 at <a href="#" class="seekto" data-time="412">6:52</a>, what if I remove the left interval instead of the right one? Does it make a difference?

@tarungopal3065 3 жыл бұрын

Superb explanation....

@techdose4u 3 жыл бұрын

Thanks

@abhisheksaraf2616 3 жыл бұрын

I think we can solve it via dynamic programming also but complexity would be N2

@shubhamagarwal8297 11 ай бұрын

What is the proof for case 2 ? we are removing one of the intervals - greedily removing which one will be better ? Its simply - earlier ending point is given preference case 2 and 3 almost same

@BravePro 10 ай бұрын

Didn't get it either. Why remove the one that starts later and ends later? I think it's about that there's more chance that it will be inside another interval later but I can't prove it. It's one of those problems that you shouldn't be thinking too much. Memorize the solution and the *trick* and that's it.

@rachitchaurasia1270 2 жыл бұрын

just a very small change in this code and we can do this problem also :) :- 452. Minimum Number of Arrows to Burst Balloons

@_inspireverse___ 2 жыл бұрын

What's the problem if sort the array in ascending order and removing the interval having larger gap.Because any interval having larger gap ka overlap with max number of intervals. Please Tell 🙏🙏

@amitavamozumder73 3 жыл бұрын

I tried to do a LIS on the sorted array :P , but this seems faster.

@aayush5474 3 жыл бұрын

Bhaiya aapne mtech ke baad samsung join kiya na? Toh abhi app sde1 ho ya sde2?

@drishtdyumnshrivastava5313 3 жыл бұрын

misssed 1 condn....btw tnks for the help

@techdose4u 3 жыл бұрын

👍

@jd3287 8 ай бұрын

what about a case 4 where for a interval, there are multiple intervals overlapping?

@dovyraj1272 3 жыл бұрын

Sir can v use , DP and longest increasing sub sequence ?

@ayushprakash8343 3 жыл бұрын

yes I have use and got the correct result but this is more efficient approach

@techdose4u 3 жыл бұрын

Yep.

@shaswatdas6553 3 жыл бұрын

need correction in 2nd cond i guess if(intervals[left][1]

@c.4469 Жыл бұрын

How do I prove that this problem can be solved with a greedy approach?

@rakshith3547 3 жыл бұрын

just wow

@techdose4u 3 жыл бұрын

😃

@sudhanshusingh211 2 жыл бұрын

can we do it by lcs by sorting by first ???

@thinkverse94 3 жыл бұрын

Nice one.. How you write in such a beautifully .. Are you using mouse only or any electronic writing pad to make video?

@techdose4u 3 жыл бұрын

Tablet

@hapysethi1306 3 жыл бұрын

Sir in case 2, can we use Interval [left] [1] > interval [right] [0]. Instead of Interval [left] [1] < interval [right] [1]

@shaswatdas6553 3 жыл бұрын

Interval [left] [1] > interval [right] [0] this does not ensure that they are overlapping case 1, and they may be overlapping case 2 also. eg: (2,10) and (3,9) 0-------L----------------1 0----R----1 here L(1)>R(0)

@pranavsharma7479 2 жыл бұрын

@@shaswatdas6553 thnks had same doubt

@vijayakumareyunni6010 Жыл бұрын

I think the total video time can be reduced by "not reading the input array elements" and avoiding explaining some simple steps. Also, the "overlapping case-3 of case-2 titles" are confusing. To understand the strategy to solve this, one need to wait almost 75% of the time! Thanks for your effort, but, with some improvements your videos will be very helpful.

@shaswatdas6553 3 жыл бұрын

Python code: def non_overlapping(arr): arr.sort(key=lambda x: [0]) left = 0 right = 1 count = 0 n = len(arr) while right < n: if arr[left][1] =R[0] ''' 0------L--------1 0----R--1 ''' count+=1 left=right right+=1 print(count) ip = [(0, 3), (2, 6), (4, 6), (6, 8)] non_overlapping(ip)