Minimum Cost to Hire K Workers - Leetcode 857 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/minimum...
0:00 - Read the problem
0:30 - Intuition
5:33 - Drawing Explanation
13:00 - Coding Solution
leetcode 857
#neetcode #leetcode #python

[@NeetCodeIO]

Sorry I missed so many days lately. I'll be much more consistent going forward. You can count on it!

[@metarus208]

pls make more coding content going forward

[@yang5843]

Would a financial incentive motivate you to make videos the day of?

[@diaaabusaada910]

We've missed you my friend😉

[@gryffindor6409]

ok

[@ik6071]

is it still possible to upload videos on the days you missed?

[@asmodeus159]

Companies asking this question in Interview ❌
Companies implementing this ✅

[@venkateshnaidu2133]

There's no way I can come up with this logic in an interview

[@prakhargupta4320]

may be with some help from the interviewer

[@visintel]

Practice heap medium level questions. It helps me to look at solutions when I’m stuck. You’re right, it’s hard to come up with this but it gets easier when you practice and study solutions. You’ll be stuck less and less with practice

[@tusharsingh3480]

3:20 "if we wanna be full capitalists"
- Neetcode

[@EduardYudinkov]

Thank you for the best explanation ever! After the first 4-5 minutes of the video, I was able to figure out a solution on my own.

[@rawatvinod4164]

this one got me confused for days but your explanations always helps me understand every problem better.

[@antm9957]

Thanks!
Don't disappear for so long.

[@JRK_RIDES]

Thanks man, your videos help a lot.

[@lakshmanprabhu6722]

Best explanation!! Thank you

[@kareemadesola6522]

Thank you for significantly reducing the time I would have spent on the editorial

[@taqihaider9879]

Best explanation !

[@iliadmitriev01]

*capitalists have left the conversation
you can get 20 units of work for the half price (50)
no, I can get 15 units for the double price (105)

[@JamesBond-mq7pd]

Yup. Absurd

[@JamesBond-mq7pd]

I have tried to solve this task for 2 hours! Unreal problem!

[@krateskim4169]

Awesome explanation

[@rostislav_vat]

thank you neetcode

[@ChickenWangTFT]

thank you king

[@CS_n00b]

very cool

[@LimpBizkit195]

I think the time complexity can be simplified as O(nlogn) since n >= k

[@barnetthan9391]

thanks goat

[@krit2038]

What about the case when the max value that you pop from the heap is the value that you have just added, in that case would it still be valid to evaluate res using the current rate?

[@aadharjain313]

same doubt??

[@siddharth-gandhi]

my guess is you can prove that total_quality * rate would be less than the res at that time, so doesn't matter. tho i havent proved lol

[@pogman1]

It's because since we know that the rates are increasing as we loop through, you can guarantee that total_quality * rate will be larger.
I.e.
the total quality was 10,
we add a new guy with a higher rate,
if we pop this guy because he has a higher quantity too, we'll basically be doing 10* higher rate which will be >= 10*prev rate

[@aadharjain313]

@@pogman1 but that won't be the minimum cost then ?

[@pogman1]

@@aadharjain313 it would be since you take the minimum. In the example I gave it would be min(10* prev rate, 10*higher rate) which is guaranteed to be 10*prev rate bc of what I mentioned

[@Munchen888]

Please help me with this question. I'm going to use sliding window starting from 1 to len(quality) . From heap I'm going to pop when : while heap and len(heap) > k, heapq.heappop(heap). But I don't realize how to check when I am heappush to heap?

[@sirajussalekin9239]

this has to be the most convoluted explanation of K workers problem I've heard 😅

[@Techgether]

Hi navdeep, any good resource recommendations to learn how to determine space and time complexity for my own created solution? and also any website that can explains DSA terminology well?

[@mariansalam]

College

[@Techgether]

@@mariansalam damn

[@kwakukusi4094]

thanks, I did not even understand the question

[@Sarwaan001]

This is very similar to a question that we ask at Disney+

[@pastori2672]

i got TLE am i a failiure ?

[@_sonu_]

Hi Bro Are you haring ?

[@chien-yucode992]

🥳🥳🥳

[@orcus_irl]

how is he using his pen(whatever) to write on browser bro can someone tell me? is there any software that is smooth as he is using right now?
I am open for suggestion regarding software

[@MrLeyt1125]

No, he drawing with a real pen on real monitor and takes video with his phone. New video = new monitor, please donate for a new vids

[@manuelscott9078]

paint 3d

[@aritrobiswas6439]

What I learned today is being too good at your job is not necessarily going to get you a job.

[@torvasdh]

This is somehow worse than current industry pay scaling, so expect to see this adopted next year.

[@juanmacias5922]

I think what makes this problem hard is the lack of explanation of what is happening in the question, and solutions haha

[@ShikaIE]

Yes the question is ridiculously confusing

[@juanmacias5922]

@@ShikaIE right! Even if they just alluded to "grading on a curve" lol

[@nikhilanand984]

while we are subtracting the maximum quality (since it's a maxheap) when the size of the heap becomes > k (k + 1), suppose our current quality is the maximum quality and we subtracted it from our total quality, but we are still using it's rate (which will be the maximum rate till now since rates are stored in ascending order) to get the minimum total wage by multiplying it with the total quality till now after the subtraction of the current maximum quality. basically we are multiplying the rate of that current quality with the total previous quality we already calculated an answer for. though this won't change our minimum answer till now since we are multiplying it with a greater rate, but still this is wrong. maybe we can also maintain a maximum quality and whenever we are popping the maximum quality, we won't use its rate to find the answer.

[@MykolaPavluchynskyi]

Yes, this bothers me as well. Maybe we should put to the heap not just quality - but pair we are processing. If if the pair we have to remove - is the same we just added - just skip it...

[@MykolaPavluchynskyi]

Probably wiser would be to delete the max element right after processing with size k, that way don't have such situation at all

[@MykolaPavluchynskyi]

Queue qualityQueue = new PriorityQueue((a,b) -> Integer.compare(b.quality, a.quality));
for (Worker worker : workers) {
qualityQueue.add(worker);
qualitySum += worker.quality;
if (qualityQueue.size() == k) {
final double biggestRateByNow = worker.ratePerQuality;
final double resultCandidate = qualitySum * biggestRateByNow;
result = Math.min(result, resultCandidate);
Worker biggestQualityWorker = qualityQueue.poll();
qualitySum -= biggestQualityWorker.quality;
}
}

[@vishaalkumaranandan2894]

I am still in some kind of confusion with the code

[@ravatez]

You are late man! I solved it but in different way. Keep posting. Don't break streak 😂

[@copilotcoder]

There is a problem, we are calculating total_quality * rate, but one of the individual wage might hit the wage cap and must be discarded?Can you explain sir

[@il5083]

It's sorted, so the previous rates (wage/quality) are lower, therefore their quality * new_rate would be >= minimum wage.

[@Benstokes555]

AHH DIDNT GET IT

[@rajsuriyang3427]

I didn't even understand this question

[@yogendrakesharwani3650]

When he does (10+5)*7=105 i was like 💀🤡☠️

[@supremoluminary]

Who just deleted my comment?

[@supremoluminary]

Put my deleted comment back up.

[@NeetCodeIO]

pretty sure yt auto deletes some, usually because of urls

[@supremoluminary]

@@NeetCodeIO I put it up four times. The fourth time, it seems to have stuck. We are no longer safe, there is a link to GitHub.

[@toseefalikhan2297]

Best explanation!