857. Minimum Cost to Hire K Workers | Priority Queue | Heap | Kinda Sliding Window
Вставка
- Опубліковано 26 сер 2024
- In this video, I'll talk about how to solve Leetcode 857. Minimum Cost to Hire K Workers | Priority Queue | Heap | Kinda Sliding Window
Let's Connect:
📱Discord (Join Community) : / discord
📝Linkedin: / aryan-mittal-0077
📸 Instagram: / codewitharyanbhai
💻 Twitter - / aryan_mittal007
🤖 Github: github.com/ary...
About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)
✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms
![АЛАУДИНОВ у Скабеевой: эти их ВСУ нас НЕ ДОГОНЯТ 😁 [Пародия]](http://i.ytimg.com/vi/an0anqU4WGQ/mqdefault.jpg)
Please do like & share with your friends or other coding communities, ifff and only if you like our videos & want us to make more such regular editorials. Your motivation to watch these videos is to get high package jobs & my motivation is your love ❤
Bhaiya you are amazing teacher...
Bechara was personal🤣. Thanku pura question ache se samajh aa gya.
Ohhh god when will I be able to solve these problems all by myself. But great explanation
One of the best explanation of a hard problem i ever saw. Thanks bro. Keep up the Good work!
The best explanation! was fun to watch how u called the lowest wage person bechara😂
bhayia slides v share krdea kro... helpfull raheta hai... notes bnane mai
one doubt @ 24:07 Since we're using the ratio of the new quantity, that quantity should be part of the quantitySum.. suppose the heap size > k and the new quantity is the greatest say 5 and we need to remove it.. in that case, what if we remove it from the heap & qualitySum and just use it's ratio?
That is an awesome question, firstly hats off to even think in such deep🫡
.
But my claim is : if quality is high of curRatio that we will have to ultimately remove from priority queue, then it will never contribute to minAns.
.
.
Conclusion: thus including or excluding this ratio will never even matter for our ans
.
.
Proof: Also proof is purely mathematically but i’ll explain with an example ( making this example generic )
.
.
Step1- as all ratios are sorted thus number these ratios as r1, r2, r3, r4. Now as they are sorted just assign them random but sorted values. r1 = 1, r2 = 2, r3 = 3, r4 = 4 (you can take any ratio values but sorted)
Step 2 - now we imagine we had to take 2 employees, and also imagine you are at 4th employee i.e. index = 3 (4th employee)
Step 3 - (Assumption to prove the fact) - Now we are saying the ith employee has higher quality & we already have lesser k qualities in the heap. Okay, lets say ith employee has quality 5, while you already had in the heap quality of 2 & quality of 1 (imagine for index 1 & 2 respectively)
Step 4 - Now as ratios are sorted in ascending order and index3 employee had a ratio of 4 (r4 = 4) and quality as 5 (just considered higher than 2 & 1), so wage which i'll be giving this 3rd index employee will be 5 * 4 = 20$
Step 5 - While if we already had a quality of 2 (taking max quality out of 2 & 1), and we also know its ration will for sure be less than 3rd employee (assumed ratio was 2), thus his wage will be 2*2 = 4 (same will follow for second employee too)
Thus, it proves, that as ratios are sorted in ascending order, this will make sure we take minRatio & multiply by minQualitySum to get minPaidSalary to these k employees.
I hope this solves the doubt.
The simple explanation is that if we removed the person and used his ratio, that means we are using a higher ratio (since sorted) in the current iteration, but using the quality from last iteration. This will never be minimum than the previous ans and won't matter in the end
best explanation for this problem
Honeslty i derive the formula that u derive , but uske baad how to use it i learnt from u👍..this is my learning
Amazing explaination , Didn't imagine I will completely understand hard problem in 1 go.
I know I am asking for lot but can you make a giude on how should I follow your intution building playlists becoz questions are arranged in cronological order and some questions are difficult to understand at first
Excellent explanation😃😃
Brilliant Aryan.
good luck, coming up with this during interview😮💨
Nice explanation ❤
Great explanation 🙌
Amazing 🔥🔥
your explanation was really good
it would have been great if you could have dry run a complete example at the end
Can anyone help me with this part?
I get it that we will find the minimum pay by sorting the ratios and maintaining a priority queue to get the min qualities, but what if that total cost that we found didn't meet the minimum wage expectation of one or more people?
We are taking values which are behind the current index and the array is sorted based so for ith element either we will pick its own ratio or a ratio bigger than its ratio which will eventually give more than its min wage
You explained it very well. Thanks a lot.
Request you to kindly also do LC 759 , 871.
great work brother.. hats off..
i don't get him after 18:00
bhaiya jhoot ni bolunga, ekdam sir k uppar se gaya ye question................LEETCODE HARD NI BANTE HAIN MUJHSE😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭😭
you should share the notes
Great Explanation, Thanks
Great Explanation!!
Excellent explanation
What should I do when I don't have such an intuition for questions like that ?
hello ji just search for that video got it in just NOW
Bilkul ji ❤, thank you ji 🫂
This dialogue holds for this awsome video "aryan bhai ke age koi bol skta hai ky....."
📢🫡📈
Thank you for explanation.
Great explanation 🔥🔥🤩
@ARYANMITTAL what happen if the i th element got removed from priority queue?
That is an awesome question, firstly hats off to even think in such deep🫡
.
But my claim is : if quality is high of curRatio that we will have to ultimately remove from priority queue, then it will never contribute to minAns.
.
.
Conclusion: thus including or excluding this ratio will never even matter for our ans
.
.
Proof: Also proof is purely mathematically but i’ll explain with an example ( making this example generic )
.
.
Step1- as all ratios are sorted thus number these ratios as r1, r2, r3, r4. Now as they are sorted just assign them random but sorted values. r1 = 1, r2 = 2, r3 = 3, r4 = 4 (you can take any ratio values but sorted)
Step 2 - now we imagine we had to take 2 employees, and also imagine you are at 4th employee i.e. index = 3 (4th employee)
Step 3 - (Assumption to prove the fact) - Now we are saying the ith employee has higher quality & we already have lesser k qualities in the heap. Okay, lets say ith employee has quality 5, while you already had in the heap quality of 2 & quality of 1 (imagine for index 1 & 2 respectively)
Step 4 - Now as ratios are sorted in ascending order and index3 employee had a ratio of 4 (r4 = 4) and quality as 5 (just considered higher than 2 & 1), so wage which i'll be giving this 3rd index employee will be 5 * 4 = 20$
Step 5 - While if we already had a quality of 2 (taking max quality out of 2 & 1), and we also know its ration will for sure be less than 3rd employee (assumed ratio was 2), thus his wage will be 2*2 = 4 (same will follow for second employee too)
Thus, it proves, that as ratios are sorted in ascending order, this will make sure we take minRatio & multiply by minQualitySum to get minPaidSalary to these k employees.
I hope this solves the doubt.
I am constantly learning new things from your videos thats why I am able to think in depth. Thank you for these awesome videos bro and awesome explanation too :)
Well Explained
How do you manage to get these questions done during a live contest?
Best explanation
meri selection ho gyi h?
Please share code solution as well
just for your reach commenting good guy
i am not getting one thing , In the code how am i making sure that i do not pick someone such that the ratio*quality of that person is lesser than his minimun wage ??
Already explained in video bro, when i told, club both the conditions thus we arrived on our final condition
if anyone don't want to share then just click on share button and copy the link, it will trick the algo.
quality* (not quantity)😭
🥲🙈
I was getting confused if quantity was another thing
Space should be :
O(n + k)
bro where are we checking that the paid amount is more than minimum wage amount?
same doubt
plz reply if got the answer
first we have taken the ratio(wage/q => wage per quality) stored in vectorworkers (dbl:ratio, int:quality). then sorted workers means for all i
@@jevinmakwana6811 got it in dry run thanks
Since we are sorting by w/q ratio,if we use w/q ratio for a quality values corresponding to higher w/q ratio,we will see that the wage for the person with high w/q ratio will go below his minimum wage value,and so this condition has to be true for every person whose w/q ratio we are looking to check.
@@jevinmakwana6811 Yes
10:30 life of a IOS user
class Solution {
public:
double mincostToHireWorkers(vector& quality, vector& wage, int k) {
vector workers;
int n = quality.size();
for(int i=0; i k){
q_sum -= q.top();
q.pop();
}
if(q.size() == k)
ans = min(ans, worker.first*q_sum);
}
return ans;
}
};
maqsad 😅
bHAI just keep the things simple, don't talk too much.
what is becha..... this.. that....
don't try to include extra unnecessary things.
bhai ise ganda explanation nhi dekha bol zyda rha hai samjha kuch nhi pa rha
Great explanation
Great Explanation !