1
00:00:00,110 --> 00:00:01,760
Hey there and welcome back.

2
00:00:01,790 --> 00:00:07,880
Let's now dive into another interesting question, which is the two city scheduling question.

3
00:00:07,910 --> 00:00:13,340
The question reads A company is planning to interview two n people.

4
00:00:13,460 --> 00:00:14,000
Okay.

5
00:00:14,000 --> 00:00:17,480
So this indicates that it's an even number of people.

6
00:00:17,510 --> 00:00:26,630
Then the question says given the array costs, where costs at I is this array over here a cost and B

7
00:00:26,630 --> 00:00:27,140
cost.

8
00:00:27,140 --> 00:00:34,520
The cost of flying the ith person to city A is a cost, and the cost of flying the ith person to city

9
00:00:34,520 --> 00:00:35,870
B is B cost.

10
00:00:35,900 --> 00:00:42,650
Okay, so it says that the array costs has elements which are arrays themselves.

11
00:00:42,650 --> 00:00:45,620
And these elements have two values.

12
00:00:45,620 --> 00:00:52,040
And the first value is the cost of flying that particular person to city A, and the second value is

13
00:00:52,040 --> 00:00:54,830
the cost of flying that particular person to city B.

14
00:00:54,980 --> 00:00:55,670
Okay.

15
00:00:55,670 --> 00:01:04,280
And the question continues saying return the minimum cost to fly every person to a city such that exactly

16
00:01:04,280 --> 00:01:06,740
n people arrive in each city.

17
00:01:06,740 --> 00:01:13,220
And then it says costs has even number of elements and the number of elements is greater than equal

18
00:01:13,220 --> 00:01:13,610
to two.

19
00:01:13,610 --> 00:01:19,370
Okay, so it's two, four, six, etc. these are the possible number of values that can be there in

20
00:01:19,370 --> 00:01:20,150
the costs array.

21
00:01:20,180 --> 00:01:21,920
It's an even number of elements.

22
00:01:21,950 --> 00:01:24,200
Now we are also given two examples.

23
00:01:24,200 --> 00:01:31,430
And in the first example if the input array is this array over here notice that we have four people

24
00:01:31,430 --> 00:01:36,950
to fly and we need two people in city A and two people in city B.

25
00:01:36,950 --> 00:01:42,200
And if this is the input array the expected output would be 75.

26
00:01:42,200 --> 00:01:49,520
And for that we'll fly the first person to city A, the second person to city A, the third person to

27
00:01:49,520 --> 00:01:52,220
city B, and the fourth person to city B.

28
00:01:52,310 --> 00:01:58,670
Now if you add up the costs involved, that would be five plus 30 plus 30 plus ten, which is equal

29
00:01:58,670 --> 00:01:59,690
to 75.

30
00:01:59,690 --> 00:02:02,120
And you will see that this is the minimum cost.

31
00:02:02,150 --> 00:02:09,200
Now if you consider all possible combinations and if you meet the constraint, which is that half the

32
00:02:09,200 --> 00:02:14,690
number of people have to be flown to city A, and the other half have to be flown to city B.

33
00:02:14,690 --> 00:02:19,430
So if this constraint is met, you'll find that this is the minimum cost involved.

34
00:02:19,430 --> 00:02:26,060
And for this example it's pretty straightforward because notice that among five and 25 is the minimum

35
00:02:26,060 --> 00:02:32,600
value among 30, and 130 is the minimum value among 430, 30 is the minimum value.

36
00:02:32,600 --> 00:02:36,080
And among 50 and 1010 is the minimum value okay.

37
00:02:36,080 --> 00:02:39,140
So in this input it's pretty straightforward.

38
00:02:39,140 --> 00:02:44,330
So we just pick this person and this person for city A because these are the minimum values.

39
00:02:44,330 --> 00:02:48,830
And these two people for city B we are also given another example.

40
00:02:48,830 --> 00:02:50,960
Now if this is the input array.

41
00:02:50,960 --> 00:02:53,810
Notice the scenario is a little bit different.

42
00:02:53,810 --> 00:03:02,900
If you were to identify the minimum cost for each person, that would be 2050, 601, 50, 104, 50.

43
00:03:02,900 --> 00:03:10,010
But notice that in this case only this is for city A, and all of these are for city B, but we can't

44
00:03:10,010 --> 00:03:15,410
fly everyone else except this particular person to city B, because that would violate the condition

45
00:03:15,410 --> 00:03:21,800
mentioned in the question, which is that half of the people have to be flown to city A, and the other

46
00:03:21,800 --> 00:03:24,440
half have to be flown to city B.

47
00:03:24,530 --> 00:03:24,980
Okay.

48
00:03:24,980 --> 00:03:30,740
So if this is the input array, the expected output is 1470.

49
00:03:30,740 --> 00:03:37,820
And you can obtain that by flying this person to city A, this person to city B, this person to city

50
00:03:37,820 --> 00:03:43,520
B, and this person to city A, and this person to city B and this person to city A.

51
00:03:43,640 --> 00:03:49,160
And in this case, you'll see that three people are flown to city A, and the other three people are

52
00:03:49,160 --> 00:03:55,490
flown to city B, and the cost involved in this case is 1470.

53
00:03:55,490 --> 00:03:59,840
And you'll see that this combination actually gives us the minimum cost.

54
00:03:59,840 --> 00:04:02,000
So this is the question we'll be given.

55
00:04:02,000 --> 00:04:06,800
The costs are a and we are asked to identify the minimum cost and return that.

56
00:04:06,800 --> 00:04:08,930
So we have thoroughly understood the question.

57
00:04:08,930 --> 00:04:12,950
Now in the next video let's discuss how we can solve this question.