1
00:00:00,110 --> 00:00:01,040
Welcome back.

2
00:00:01,040 --> 00:00:06,470
Let's now implement the solution for the two city scheduling cost problem okay.

3
00:00:06,470 --> 00:00:08,330
So we are given this costs array.

4
00:00:08,330 --> 00:00:12,230
And every element in this array over here is an array itself.

5
00:00:12,230 --> 00:00:14,120
And it will have two elements.

6
00:00:14,120 --> 00:00:14,330
Right.

7
00:00:14,330 --> 00:00:16,970
So every element over here in this array will have two elements.

8
00:00:16,970 --> 00:00:20,180
And the first element represents the cost to city A.

9
00:00:20,300 --> 00:00:23,360
And the second element represents the cost to city B okay.

10
00:00:23,360 --> 00:00:24,830
So that's given in the question.

11
00:00:24,830 --> 00:00:29,750
Now the way that we are going to approach this is that we are going to sort the costs array which is

12
00:00:29,750 --> 00:00:35,690
given to us, and we are going to sort it by the difference between these two costs for every element.

13
00:00:35,690 --> 00:00:37,820
So let's go ahead and implement that.

14
00:00:44,420 --> 00:00:45,020
Okay.

15
00:00:45,920 --> 00:00:49,370
Now let's say the initial cost is set to zero.

16
00:00:49,370 --> 00:00:54,050
And what we will be doing is we will be just going through the first half of elements.

17
00:00:54,050 --> 00:00:57,920
So let's say it is cost dot length divided by two okay.

18
00:00:57,920 --> 00:01:01,460
So for the first half of elements we will just pick city A.

19
00:01:02,090 --> 00:01:11,120
So for let I is equal to zero I less than n I plus plus we're just going to say cost plus is equal to

20
00:01:11,120 --> 00:01:17,330
costs I at index zero which is equivalent to sending that person to city A.

21
00:01:17,540 --> 00:01:22,430
And for the remaining half we're just going to send people to city B okay.

22
00:01:22,430 --> 00:01:24,380
So I is equal to n.

23
00:01:24,860 --> 00:01:35,120
Let's say I less than two into n and I plus plus and cost plus is going to equal costs at index I at

24
00:01:35,120 --> 00:01:39,380
index one, which is the cost for sending that person to city B and that's it.

25
00:01:39,380 --> 00:01:42,350
And then we would just return costs okay.

26
00:01:42,350 --> 00:01:44,390
So this is how we can solve this question.

27
00:01:44,390 --> 00:01:48,230
Now let's go ahead and run this code and see if it's passing all the test cases.

28
00:01:53,140 --> 00:01:54,820
And you can see that it's working.

29
00:01:54,820 --> 00:01:56,500
It's passing all the test cases.

30
00:01:56,500 --> 00:02:00,340
And notice we have used a greedy approach to solve this question.