Non overlapping intervals | Leetcode

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

[@amalsalim88]

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]

Welcome :)

[@shaleen0mishra]

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

[@user-oy4kf5wr8l]

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

[@justshanky3012]

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

[@yjj410]

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]

Seems the same.

[@shubhamrathi3734]

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.

[@K_EC_AushoRoup]

16/18 test cases passed. I am here because of the remaining test cases.
Update:
And @7:25 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]

Welcome :)

[@deepanshjohri3997]

Thanks alot sir, I stopped the video at 11:47 and implement the whole code by myself
🙏🙏

[@paragroy5359]

Thanks a lot for making such videos.
Great Content

[@adityaojha2701]

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

[@techdose4u]

👍🏼

[@girikgarg8]

In overalapping case 2 at 6:52, what if I remove the left interval instead of the right one? Does it make a difference?

[@vcfirefox]

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]

Thanks 😊

[@imranimmu4714]

Couldnt have found bettter explanation.
Thank you.

[@pryansh_]

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

[@johncenakiwi]

Amazing explanation. Coded it with ease. Thank you !

[@techdose4u]

Welcome 😊

[@shayestaparveen315]

Thanks!

[@codelite700]

Wow, this was much more intuitive.

[@nitishprasadkushwaha]

u are the saviour

[@alltechsimplified2134]

amazing explanation as always

[@pranavsharma7479]

all intervals problems are solved by this template thanks a ton

[@rakeshsahni_]

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

[@techdose4u]

Welcome :)

[@Ice-2706]

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

[@techdose4u]

Thanks

[@kaushaljalan2928]

Great effort put up for such an awesome explanation.

[@techdose4u]

Thanks :)

[@ekengineer9868]

Awesome Explanatoin

[@krishnakantsharma6161]

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

[@techdose4u]

Thanks

[@prasad.patil12]

Simple and clear explanation 👍

[@techdose4u]

Thanks :)

[@joshithmurthy6209]

thanks

[@InvincibleMan99]

Thanks

[@hardiksardhara3355]

Great explanation

[@techdose4u]

Thanks

[@rachitchaurasia1270]

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

[@shubhamagarwal8297]

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]

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.

[@abhisheksaraf2616]

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

[@_inspireverse___]

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

[@therealaspirant1882]

awesome explination bro

[@techdose4u]

Thanks

[@tarungopal3065]

Superb explanation....

[@techdose4u]

Thanks

[@Voice_Of_Thoughts]

Nice explanation

[@techdose4u]

Thanks

[@shaswatdas6553]

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?

[@jd3287]

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

[@amitavamozumder73]

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

[@dovyraj1272]

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

[@Ice-2706]

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

[@techdose4u]

Yep.

[@drishtdyumnshrivastava5313]

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

[@techdose4u]

👍

[@sudhanshusingh211]

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

[@aayush5474]

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

[@rakshith3547]

just wow

[@techdose4u]

😃

[@thinkverse94]

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

[@techdose4u]

Tablet

[@hapysethi1306]

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

[@shaswatdas6553]

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]

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

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)