Interval Scheduling Maximization (Proof w/ Exchange Argument)

[@BackToBackSWE]

Table of Contents: Introduction 0:00 - 1:22 Greedy Algorithm Walkthrough 1:22 - 5:14 What We Want To Prove 5:14 - 7:03 Exchange Arguments 7:03 - 7:33 The Proof 7:33 - 11:30 Trying To Exchange 11:30 - 16:20 Finishing The Argument 16:20 - 19:24 Conclusion 19:24 - 20:17

[@maythecodesbewithyou29]

great video man

[@BackToBackSWE]

thanks

[@amitbhogal7406]

This is an award-winning explanation if one considers the patience, thoughtfulness and elocution with which it has been done. God bless your continued efforts in education!

[@sankalparora9261]

I have never seen so in-depth understanding of Interval Scheduling ANYWHERE! Keep killing it!!! THANKS, A LOT! "By the very nature we are doing something, there can be no conflict" hit me the most.

[@BackToBackSWE]

ye - lol nice

[@spectermakoto9029]

This channel is a goldmine Just really exceptional stuff clear, concise and fun to watch

[@BackToBackSWE]

thx

[@MMOlocation]

Your channel and leetcode got me an internship at facebook. Thank you dude, keep it up!

[@BackToBackSWE]

Excellent, have fun there!

[@krishnnasarrdah3534]

fr? how did you apply? can you help me out?

[@maythecodesbewithyou29]

congrats

[@hsinyang1796]

congrats!

[@amanial-khalifa5299]

Can you believe that I have attended two 2 hour lectures about greedy algorithm and I have just understood it in this 20 minutes video! Thank you!

[@peterren5409]

This man has helped me with my algo class more than anyone else

[@ashelytang2592]

I have an Algorithms Midterm tomorrow and I found this video to be super helpful! I could understand everything you were saying! Simple and straightforward explanations are the best!!! Thank you for this!

[@BackToBackSWE]

Nice

[@acspd7]

Just wanted to let you know you are God's gift to mankind. I can really tell you have a genuine passion to teach and help others. Not some scumbag (which there are many, unfortunately in this industry) looking to cash in on exploit tech job seekers because the market is fiercely competitive these days. And even if you did end up charging for your course, I'd still pay for it because you come from a good place. Great work.

[@BackToBackSWE]

Haha, um, I mean I am morally dubious certain days, mostly not. And yeah lol, I don't really think about anything I'm doing...I'm just doing

[@Messirobben047]

Best problem-solving channel on KZbin. Brilliant stuff!

[@dotanoob466]

Excellent! As a person with a background in math who now works as a software dev who’s looking for a new job, this was great. Underneath it all, at its fundamental level, i think this a proof by induction. Very well explained!

[@brandenhernandez7772]

been watching all your videos for my final and man you explain 16 weeks of school better in a 20 min video.

[@crazytourist6619]

I just fell in love with this explanation !!!

[@maripaz5650]

binge-watching your videos before a final round interview. thank you very much! your videos have helped me get so much further this recruiting season.

[@BackToBackSWE]

great

[@johnleonardo]

dude, your explanations are out of this world! you’re helping me with interview prep so much. thank you & subbed, liked. this channel is en route to blowing up!

[@BackToBackSWE]

haha thanks, and nah, it is steady growth so slowly but surely

[@leakyshoes8297]

Love this. Wish it would show a written proof with induction. Only saying this because there was a lot of talking, but putting this into a written proof is a bit mind bending. However, absolutely thumbs up and subscribed!

[@zhangxuewei7554]

dude, you are born to be a teacher!

[@MuffinLucas]

You're such a talented teacher, than you for these wonderful videos!

[@jpfsilva]

These videos of him are amazing! He explains perfectly well and understandable. Thanks for that!

[@BackToBackSWE]

thanks

[@Nima-Salami]

Duuuude! The best explanation I've found on Exchange Argument! God bless you!

[@Amy-tw3zh]

This makes good sense. I had to picture in my head the diagram or examples as you explained all the WHY's, to convince myself that it's always true. And indeed it is. It's hard to think about application of this to other algorithms though.

[@BackToBackSWE]

ye

[@Dryicicles]

Jesus Christ what an incredibly fresh cut

[@tofahub]

You are an algorithmist. Such an inspiration!

[@BackToBackSWE]

Lol, no, I'm just an average dude who recorded a lot of videos

[@devinshaw8558]

Very hard to build an intuition for this, but this video is closest I have seen.

[@weizhao8214]

I really should have watch this video before my midterm

[@BackToBackSWE]

hey

[@kumarutkarsh4016]

Consider a variant of this question. We are supposed to find intervals giving the max cardinality as before. But the added constraint is that in the case of two solutions having the same cardinality, we need to pick the solution where the length of time covered by all the intervals is lowest. What modifications (if any) to the current algo would be required?

[@BackToBackSWE]

im not sure I barley remember this video im sorry

[@kumarutkarsh4016]

@@BackToBackSWE Oh, no issues.

[@srishtijain1092]

Amazing video! Thanks for the wonderful content always!

[@BackToBackSWE]

sure

[@user-rf4vc7mt4d]

I wish you were my professor. This is sooo helpful

[@BackToBackSWE]

sure

[@nguyentuan1990]

I dont understand, so everything is the same from G to O until k-1 but k is where everything diverge ? how can you say that the finishing time fo G(k)

[@shizibaozi]

such a great and clear explain, even though I am poor at English can understand.

[@BackToBackSWE]

Happy Halloween 🎃 Thank you for your kind words, shizibaozi! What languages do you speak? You get some extraaa treats for the hardwork - 50% Off our exclusive lifetime membership use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50

[@Leo-tz7lp]

MAN was this video well made, thank you.

[@BackToBackSWE]

Glad you enjoyed it!

[@anonymoussloth6687]

i had a similar problem, but i cant find a solution to this anywhere. in fact, i cant even find the problem anywhere (i originally saw this problem on my university test). the problem is, u r given n jobs with start and finish times, and u have to find the minimum number of processors that can finish all jobs. a processor can only do disjoint jobs (jobs that don't overlap). Sample test case: There are 5 jobs (with start and end time given respectively): 1 11 2 3 3 6 4 6 10 13 The answer is you need a min of 3 processors to complete all the jobs. processor 1: 1-11 processor 2: 2-3 4-6 10-13 processor 3: 3-6

[@adityasrivastava8790]

Hey John Legend! Keep up the Good work my man!!

[@BackToBackSWE]

ok

[@adityasrivastava8790]

@@BackToBackSWE "ok", *seriously?!

[@sitanshushukla1820]

Your explanations are the best!!!

[@BackToBackSWE]

sure

[@nawendusingh2858]

watching this tonight coz i have finals tomorrow.thanks for such a great explanation. Have u done interval partitioning as well?

[@BackToBackSWE]

na

[@andywang4189]

Thanks, this is best explanation of the proof

[@BackToBackSWE]

sure

[@OrangePotatoLeo]

Great job explaining!

[@ananydwivedi5853]

Very good explanation, thank you!

[@benzeltser9851]

I need to rob my University, take all what I've paid them, and hand it all to you

[@BackToBackSWE]

Hahaa

[@DheemanSaha]

Well I was not cleared how you made sure your greedy solution is the optimal solution. Is it possible to share more information?

[@BackToBackSWE]

I forgot the contents of this video but loosely remember that it had to do with an exchange argument. Fast replying to comments cant address

[@top-list6450]

Thanks for these amazing videos . could you also add the question link, so that we can try

[@BackToBackSWE]

I don't have a link for it

[@shanness237]

Crystal clear!!!! Thank you!

[@BackToBackSWE]

nice

[@anhduy7367]

This helps me a lot. Thank you

[@BackToBackSWE]

great

[@praveenchouhan6388]

so this looks like a combo of greedy and dynamic programming right???

[@ahonhuman3717]

Incredible video! Thank you!

[@BackToBackSWE]

Happy Holidays 🎉 Thank you for your kind words, ahonhuman! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40

[@adods4058]

Good job. Well explained

[@BackToBackSWE]

thanks

[@EliseGreen-tz2qe]

Very clear explanation!

[@BackToBackSWE]

Happy Halloween 🎃 Thank you for your kind words, EliseGreen! Let us know other topics we could cover! We'd love to offer you 50% Off our exclusive lifetime membership use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50

[@arpithparikh]

can we say Greedy Exchange is the most efficient solution?

[@BackToBackSWE]

I'm not sure? Efficient asymptotically or in terms of real elapsed time? If the former it'd have to be, because linear time is the lower bound, we have to inspect all intervals.

[@TomChan-nn7mu]

you save my life

[@squadbustersgamings]

Nice video, could you do a video on Weighted Interval Scheduling?

[@BackToBackSWE]

Yes, I just don't have the time though. If you have . aquestion I can answer it here

[@squadbustersgamings]

No question! Your explanation is really good btw! I was just having a hard time understanding weighted interval scheduling and hope you can do the video on this when you are free :)

[@BackToBackSWE]

@@squadbustersgamings ye

[@abdelrhmangamal3018]

شكرا صاح! عمال ساعة بحاول افهم بس انت راجل صح الصح وفهمت خلاص الحمد لله.

[@xinyucao5550]

Great explanation!

[@BackToBackSWE]

thx

[@paiqu3933]

Thank you so much for the video!

[@BackToBackSWE]

sure

[@anonymoussloth6687]

I am a little confused. Does an exchange mean that ur are sawing 2 events? Or are u inserting one and still keeping the other? For ex, gk and bk, did u put gk in optimal set and still keep bk after it or did u replace bk by gk?

[@vasiliinikonov6477]

He spoke of the code in the description, but I cannot find it

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com.

[@shahainmanujith2109]

Nice explanation :)

[@אסףוטרמן]

great explanation thank you :)

[@tommieb8623]

Is there also a greedy method for maximization of the intervals length instead of the amount of intervals?

[@BackToBackSWE]

not sure

[@JustixLoL]

I guess in this case you need to exchange previously chosen interval with current if it is smaller then current and continue

[@alexandra4629]

Thank you so much.

[@prachurjyakashyap2029]

You got a subscriber

[@BackToBackSWE]

I'm blessed

[@hiteshnagothu887]

Thank you so much!!!

[@BackToBackSWE]

sure - thanks for watching

[@1234rajan1234]

thanks i get it now bro

[@BackToBackSWE]

nice

[@BeatYourYesterday]

great work

[@susmitjaiswal136]

aaammaazzinggg...got it perfectly

[@poojasadevra3893]

I think I kinda got what optimal substructure means here ..

[@BackToBackSWE]

nice

[@yoshi4980]

too late :'(

[@BackToBackSWE]

haha, indeed

[@ANGELINK999]

I understood the first part (the algorithm explanation) but not the one where you compare the Optimal vs the Greedy one. I guess I need to see it more times. Haha. Anyways, awesome work!

[@BackToBackSWE]

The notation & abstract academic nature of proofs confuse at first. Most take a bit to sink in.

[@sumukhbhat1641]

Why sort by finish time and not by start time? I sorted by start time and it cost me a coding round :(

[@ahm_adash_i6723]

thank you sir

[@malikfahadsarwar2281]

how you can say that fgk

[@dotanoob466]

Subscribed.

[@yoonchaena671]

you save me thanks

[@pranavsingh9284]

very much thanks sir

[@alantao6895]

where the heck is the code? 🤔

[@BackToBackSWE]

repository is deprecated, we do not maintain it but it is still on my github

[@MathAfta]

Hero !

[@InfernTech]

so good

[@ankithreddyadudodla7673]

cool and nice

[@BackToBackSWE]

thanks lol

[@maxbarahona9675]

What is your leetcode username?

[@BackToBackSWE]

leetcode.com/bephrem/

[@nikmitsioris9809]

godlike!!

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@souravprajapati4578]

bro the implementation ? the code?

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@maheshg3619]

waiting for your video

[@BackToBackSWE]

wassup

[@arunm619]

Burst balloons dp problem please post

[@BackToBackSWE]

@@arunm619 yessir

[@supamdeepbains5172]

sup bro?

[@BackToBackSWE]

hi

[@furyzlm7853]

W

[@aidan618]

Great explanation but why does he explain this like a tech bro hahaha

[@ahsanulameensabit]

Good explanation :|

[@BackToBackSWE]

thx

[@praveenchouhan6388]

unclear!!!!!!!!!!!!!!!!!

[@BackToBackSWE]

ok!