Non overlapping intervals | Leetcode

[@shayestaparveen315]

Thanks!

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

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

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

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

[@paragroy5359]

Thanks a lot for making such videos. Great Content

[@adityaojha2701]

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

[@techdose4u]

👍🏼

[@大盗江南]

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

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

[@codelite700]

Wow, this was much more intuitive.

[@johncenakiwi]

Amazing explanation. Coded it with ease. Thank you !

[@techdose4u]

Welcome 😊

[@krishnakantsharma6161]

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

[@techdose4u]

Thanks

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

[@kaushaljalan2928]

Great effort put up for such an awesome explanation.

[@techdose4u]

Thanks :)

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

[@prasad.patil12]

Simple and clear explanation 👍

[@techdose4u]

Thanks :)

[@pranavsharma7479]

all intervals problems are solved by this template thanks a ton

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

[@rachitchaurasia1270]

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

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

[@ekengineer9868]

Awesome Explanatoin

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

[@AI_for_funn]

u are the saviour

[@hardiksardhara3355]

Great explanation

[@techdose4u]

Thanks

[@jd3287]

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

[@_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 🙏🙏

[@shaswatdas6553]

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

[@abhisheksaraf2616]

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

[@therealaspirant1882]

awesome explination bro

[@techdose4u]

Thanks

[@tarungopal3065]

Superb explanation....

[@techdose4u]

Thanks

[@c.4469]

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

[@Voice_Of_Thoughts]

Nice explanation

[@techdose4u]

Thanks

[@InvincibleMan99]

Thanks

[@aayush5474]

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

[@drishtdyumnshrivastava5313]

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

[@techdose4u]

👍

[@sudhanshusingh211]

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

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

[@amitavamozumder73]

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

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

[@rakshith3547]

just wow

[@techdose4u]

😃

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

[@joshithmurthy6209]

thanks