Hey there and welcome back.
Let's now dive into another interesting question, which is the two city scheduling question.
The question reads A company is planning to interview two n people.
Okay.
So this indicates that it's an even number of people.
Then the question says given the array costs, where costs at I is this array over here a cost and B
cost.
The cost of flying the ith person to city A is a cost, and the cost of flying the ith person to city
B is B cost.
Okay, so it says that the array costs has elements which are arrays themselves.
And these elements have two values.
And the first value is the cost of flying that particular person to city A, and the second value is
the cost of flying that particular person to city B.
Okay.
And the question continues saying return the minimum cost to fly every person to a city such that exactly
n people arrive in each city.
And then it says costs has even number of elements and the number of elements is greater than equal
to two.
Okay, so it's two, four, six, etc. these are the possible number of values that can be there in
the costs array.
It's an even number of elements.
Now we are also given two examples.
And in the first example if the input array is this array over here notice that we have four people
to fly and we need two people in city A and two people in city B.
And if this is the input array the expected output would be 75.
And for that we'll fly the first person to city A, the second person to city A, the third person to
city B, and the fourth person to city B.
Now if you add up the costs involved, that would be five plus 30 plus 30 plus ten, which is equal
to 75.
And you will see that this is the minimum cost.
Now if you consider all possible combinations and if you meet the constraint, which is that half the
number of people have to be flown to city A, and the other half have to be flown to city B.
So if this constraint is met, you'll find that this is the minimum cost involved.
And for this example it's pretty straightforward because notice that among five and 25 is the minimum
value among 30, and 130 is the minimum value among 430, 30 is the minimum value.
And among 50 and 1010 is the minimum value okay.
So in this input it's pretty straightforward.
So we just pick this person and this person for city A because these are the minimum values.
And these two people for city B we are also given another example.
Now if this is the input array.
Notice the scenario is a little bit different.
If you were to identify the minimum cost for each person, that would be 2050, 601, 50, 104, 50.
But notice that in this case only this is for city A, and all of these are for city B, but we can't
fly everyone else except this particular person to city B, because that would violate the condition
mentioned in the question, which is that half of the people have to be flown to city A, and the other
half have to be flown to city B.
Okay.
So if this is the input array, the expected output is 1470.
And you can obtain that by flying this person to city A, this person to city B, this person to city
B, and this person to city A, and this person to city B and this person to city A.
And in this case, you'll see that three people are flown to city A, and the other three people are
flown to city B, and the cost involved in this case is 1470.
And you'll see that this combination actually gives us the minimum cost.
So this is the question we'll be given.
The costs are a and we are asked to identify the minimum cost and return that.
So we have thoroughly understood the question.
Now in the next video let's discuss how we can solve this question.