Using Greedy Algorithm to Solve Two City Scheduling problem

Problem Statement

A company is planning to interview 2N people. Given the array costs, the cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

Example 1:

Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Constraints:

• 2 * N== costs.length
• 2 <= costs.length <= 100
• costs.length is even.

Greedy Solution

1. Assume flying all2N persons to City A and compute the total cost

tatal_cost =  10 + 30 + 400 + 30 = 470

Now, we need to swapN persons to cityB. So which persons to choose?

2. Calculate a refund array when we swap all the flying tickets from the city A to city B.

diff person1 = 20–10 = 10
diff person2 = 200–30 = 170
diff person3 = 50 - 400 = -350
diff person4 = 20 -30 = -10
diff = [10, 170, -350, -10]

Here, a positive refund means we need to pay more, a negative refund means we will get refund money.

3. Sort the refund array

diff_sorted = [-350,-10,10,170]

4. To get the minimum total cost, the more refunded the better. Pick N persons which have the least diff and make a change to fly them to City B instead of City A

5. Update the total cost after the change

update total cost = 470 + (-350) +(-10) = 110

Here comes the code

Extended Question

What if this question is modified to 3 cities? Will the greedy algorithm still work?