Minimum Time to Repair Cars - Leetcode 2594 - Python

0:00 - Intro
1:00 - Understand Problem
2:02 - The Equation
4:00 - Binary Search
10:15 - Example Dry Run
11:42 - Coding Explanation

leetcode 2594

#neetcode #leetcode #python

[Kaviarasu_S]

After more than one year of consistently solving leetcode daily problems, I seem to have finally reached a point where watching neetcode videos feels relaxing😎

[michael._.]

Honestly speaking I wouldn't have recognized this problem to be solved by binary search if I didn't solve the last few dailys.

[Medicore]

One slight optimization we can do is to pick the smallest rank element to calculate the upper limit of our search space as it would reduce the size of search space while maintaining the minimum time within the space.

[rhitambhuiya]

you can also take low as min(ranks) since we want to give the most efficient mechanic atleast one car, and the high can be set to min(ranks) * cars * cars, as to the case when we assign all the cars to the most efficient mechanic.

[KedarKhati]

A week ago I couldn't even imagine how binary search could be applied to these type of questions. But today I solved this on my own.
Thank you Neetcode.

[varane]

Thanks to the past week's daily binary search challenges, I was able to solve this problem on my own. Feeling proud!

[Kuramas_Chakra]

My boss makes a dollar, I make a dime,
That's why my Algorithm runs in exponential time.

[BehavioralFallacy]

Felt like dynamic programming reading the PD.

[swordofgrayskull]

You're relentless man, how do you keep going?

[lukmanyahya]

Returning left works too, instead of storing it in res

[ROHITKUMAR-ect]

7:37 so could reach till this point, found my upper bound myself, just feeling Happy I can think like him now.

[Whatthetrash]

Thank you! I got the binary search part but I didn't know how to do the "inner logic". Thank you again!

[sanchitmishra]

Was it just me or was finding the range and how to use that range a bit difficult in this even though I knew the pattern from the first second

[cjw]

It can be optimized by setting the right value of range to min(ranks)*cars**2 because we can guarntee it's the best worst case to repair all cars using the single fastest machine.

[omargamal]

Upper bound can be the fastest mechanic repairing all cars, so minRank not max

[DBagg-zzip]

I did the min heap way at first because it's similar to a basic job scheduling problem I encountered in a personal project (game AI estimating opponents' time to build things). Got the worst submission time but it passed and is still quasilinear, I guess.

[jaatharsh]

thanks you once again for saving my Sunday

[yashwantmoharil]

I used heap, was not efficient but passed

[reydavid]

Interesting technique. Basically you define a function and run a Newton technique to found the zero value.Your task is to find the zero value of f(t) - cars, where f(t) is quantity of cars repaired in t time and cars just the total cars to be repaired. Newton technique is just binary search.

[MP-nyep]

Terrific explanation as always. Thank you