What's going on, guys, in here?
I'm here with my little assistant, and we are going to solve a more special and a little bit different
problem.
Only God, which is an interview question as super often by companies like Amazon, Google and Facebook.
And it is called the minimum cost to hire key workers and make sure you stick till the end of the video
because they have a special giveaway for you.
Let's jump into an airbag.
Three days.
And then, as you can see, the problem is stark.
This heart, but no problem, is too hard for us, right?
So there are N workers and the IFE worker has a quality quality of I and the minimum wage expectation
wage of.
Right.
Because everybody has minimum wage expectations.
Now we want to hire exactly.
Key workers to form a paid group.
When hiring a group of key workers, we must pay them according to the following rules.
And the first rule is every worker in the paid group should be paid in the ratio of their quality compared
to other workers in the paid.
So this can be a little confusing.
Let me explain it a little better now.
Let's say you have two workers, right?
Worker, a worker bee.
What this means that worker eight is paid in the ratio of their quality compared to worker bee.
Is that the wage of the worker?
A divided.
To the quality of the worker.
A should be equal to the wage of the worker.
Be divided to the quality of the worker bee.
And this should hold for every pair of workers you choose in your set.
Right now the second condition is that every worker in the paid group must be paid at least their minimum
wage expectation.
Definitely return the least amount of money needed to form a paid group satisfying the above conditions.
Okay.
And the first example is we have free workers.
Their qualities are 10, 25.
And their minimum wage is 70, 50, 40.
And K equals two.
Now their answer is one hundred and five.
And they say we are choosing the zero worker and the second worker.
Right.
Based 70 to the zero and pay forty five to the second.
First of all, 70 plus forty five is one hundred and five.
And let's check the first condition.
Seventy divided by the quality of the zero worker, which is 10 equals seven.
Forty five.
Divided to the quality of the second worker reaches five.
Equal seven.
Segment seven equals seven which is right.
Now let's check.
Example number to five workers.
The qualities are their wages are there and K equals free and they are choosing the zero worker.
The second and the fourth worker.
Perfect.
Now we pay for the zero worker.
That means four divided by its quality, which is free.
Should be equal to thirteen point free, free, free period, free.
Divided by the second, which is 10 and free point period free.
Divided by 10, which holds.
Right.
So these are the example, guys.
Now, let's jump to the solution.
And I'm going to take the first rule because it's the most important one.
And rewrite it a little bit.
Now, what did we say?
The first rule means that the wage of the first worker divided by its quality is going to be equal to
the wage of the second worker, divided by its quality and so on and so forth, going to be equal to
the wage of the Kafe worker divided by its quality.
Right.
So all of those are going to be equal to, let's say, an X.
And what do you think this X is going to be?
This X is going to mean the wage poor quality unit.
Right.
So if I have a worker which has quality 10, its final wage is going to be ten crossed X.
So if I have a group of K paid workers, the amount of money that I need to pay all of them is the total.
Some of their qualities cross this X, but I don't get to choose this X.
This X is going to be based on the minimum wage expectation.
Right.
So if let's say I have a worker and he has a minimum wage expectation.
Right.
And the quality.
This means that the minimum X expectation for this worker.
Right.
So the minimum wage per quality unit expectation for this worker is going to be the mean wage expectations
divided by its quality.
And each worker has this number, this property.
Know I know the formula for the amount of money I have to pay my group of gay workers.
And it is if I choose workers, I have to take the maximum between those minimum X expectations in order
for all the workers to be satisfied.
Right.
So the maximum between Min X expectation for everybody crossed through.
As we said, the sum of their qualities.
So sum of qualities.
So this brings me the following idea.
For each worker.
Instead of knowing its minimum wage expectation and its quality, it's more useful to know its minimum
X expectation and its quality and sort all of this by the minimum X expectation.
Now, if I do this and afterwards I choose K workers, let's say their indexes are I want less than
two less than the other dog, less than Iki.
I know that that maximum.
Between all those minimum X expectations is going to be the mean X expectation of IRCA because we sorted
them increasingly crossed the sum of all this.
Right.
So let's say quality of I1 plus quantity of I2 plus dot, dot, dot plus quality of IKing.
And I need to minimize this brother.
Now in order to do that, I need to know at least one information and I'm going to choose min x expectation
of IKI.
So in order to know this, I should fix.
Of course I.
Right.
So I will make a for loop in which I fix the index of the last worker that I take in this way.
I know the minimum X expectation and what remains is to choose K minus one.
Other workers will have their indexes between position one and position.
I keep minus one.
Such as the sum of their qualities is minimal.
So what does this mean, that I will choose the key minus one workers with the minimum qualities from
this range?
So I'm iterating for my workers and for each worker.
I need to know the first minimum key minus one numbers.
And how do I do that?
Well, let's say I am with some current worker and I have my set of key minus one of minimum qualities
when I go to the next worker.
Now, the quality of that previous worker becomes available.
So what could actually happen is that this quality should be part of the set.
So this quality is less than the maximum number from this set.
So I should remove that number and insert mine.
So I'm going through the data structure, which holds for me those key minus one numbers, which allows
me to know very fast what is the maximum number between those, allows me to remove it if necessary
and allows me to insert elements into it.
And you've guessed this is a max hip or in the SDL library.
We call this a priority.
So we are using a priority queue.
We are iterating for workers after sorting them by the minimum X expectation.
And for each current worker we check if there are exactly K minus one quantity, it's in our priority
queue.
And the maximum quantity is greater than the quality of my previous worker.
I should insert that and remove this one.
I should add to sum.
And in the end, for each current worker.
So for each possible minimum X expectation, we are updating our answer.
Let's write the code for it now.
We are initially given the vector of qualities, the vector of wages and our Kate.
And as we said, we are going to redefine those workers as being X and quality.
So first of all, let's take the number of workers, which is the size of these vectors.
So any good is quite that size.
Then I will define another vector of pairs of double and integers, which are going to be called workers.
And for each worker, starting from position zero all the way to position and plus plus in those new
vector workers, I am going to add a new element, which is a pair of double.
And these X, as we said, is the minimum wage expectation divided by the quality of this worker.
And the second one is just going to be the quality.
Right.
So quantity of I.
Perfect.
Now, second step, we are going to sort this workers.
So workers that begin all the way to workers that end.
And as we know, when we are sorting pairs, they are going to be compared by the first element.
And then by the second one, which exactly what you want here.
So I am going to have my variable sum, which is always going to be the sum of my qualities.
So the sum of those minimum key qualities.
And my answer initially, my first valid set is consisting of the first caseworker's.
Right.
So I am going to throw those first caseworker's Opus Plus and I am taking them into my set.
So some plus equals is going to be workers of I dot second, which is the quantity.
And I'm going to insert this quality into my protocol.
So as defined that first.
So priority queue of it is going to be consisting of integers.
Let's say mean qualities, perfect, not mean qualities, mean qualities that push of workers of either
the second.
Perfect.
After this, let's initialize our answer.
So answer is going to be equal to some cross workers of K minus one.
That second.
Right.
So it's always the sum of the qualities crossed that maximum mean X expectation.
And after this, let's iterate for the other workers.
So starting a position K all the way to position and minus one plus plus.
And what shall we do here.
We will take the maximum quality from our priority.
So integer max quality is mean quantities dot top.
We are comparing this max quality.
And see if it's greater actually than workers of I got second.
And if there is, we should remove it and insert the new one.
So we are going to have here mean qualities that op.
So remove that one.
Mean qualities that push of the new one.
Workers of I don't second.
Right.
And we are going to update our some super important.
Don't forget that.
So some plus equals is going to be equal to.
I'm going to have workers of idot second minus what I have removed, which is the max quality.
Max quality.
Perfect.
After updating the sum I should add videos or two.
So the answer is minimum between the answer and some crossed this current word curse.
X.
Right.
So in the end, after doing this, I should return my answer.
And let's run the code for this.
Fingers crossed.
Let's see if it works or not.
And it does and it's I mean it.
I've already sold it three months ago.
So it's quite fresh.
Let's say.
And I have a wrong as so.
Big mistake here.
This is going to be forced to.
Right, because I'm taking the axe.
Now, let's I mean, this one.
Oh, for the best now.
And it gets first of the 90 percent.
Wow, this is awesome.
All right, guys, this was the problem.
Minimum cost to hire workers.
It is, again, either a question or need called as super often by Amazon, Facebook and Google.
And now for the special giveaway.
You just have to share this video on Facebook and write me in the comments.
What is your favorite delete code problem?
Also, guys, make sure to support this channel.
And if you really like the content, hit that like button, hit the subscribe.
And I can't wait to see the next video like.