[Problem Solving] Two City Scheduling

We are given a list of costs as shown below.

costs = [[10, 20], [30, 200], [400, 50], [30, 20]]

• The cost of flying the i^th person to city A is costs[i][0]
• The cost of flying the i^th person to city B is costs[i][1]

A company is planning to interview 2N people. Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

Example:

Input: [[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.

Assumption:

The costs list will always have an even length.

Solution:

First let’s try to understand the problem statement clearly.

• What we need to do is out of N given people and their costs, exactly N/2 people should be flown to city A and other N/2 people need to be flown to city B.
• This means for N/2 elements in the costs list, we have to choose the costs[i][0]^th element and for the other N/2 elements, we need to choose the costs[i][1]^th element.
• The part that needs to be solved is to choose elements such that the overall cost is minimized.

The first thing that pops in our heads is to find out if we can somehow sort this given list. Let’s look at an example.

[[10, 20], [10, 20], [10, 40], [10, 50]]

We can sort by the first element of the list of lists ie., costs[i][0]. This will ensure that the list is sorted by the lowest costs to fly to city A. In this case, the list remains the same.

[[10, 20], [10, 20], [10, 40], [10, 50]]

If we choose the first N/2 people this way to fly to city A and the next N/2 people to fly to city B, we are not guaranteed that the sum of costs to fly to B will be minimum.

Sum(A) = 10 + 10 = 20

Sum(B) = 40 + 50 = 90

Total cost = 20 + 90 = 110 Wrong answer!

In order to get the optimal cost, we have to fly the first two people to city B and the next two to city A. Remember that we cannot fly the same person to both city A and city B!!

Sum(A) = 10 + 10 = 20

Sum(B) = 20 + 20 = 40

Total cost = 20 + 40 = 60 Voila!

Using the given elements in the list, we cannot directly sort it such that the cost is minimized. So, what can we do with the given values? Let’s look at the costs on a case by case basis.

[10, 20] – The cost of sending this person to city A vs city B is 10 – 20 = -10

[10, 20] – The cost of sending this person to city A vs city B is 10 – 20 = -10

[10, 40] – The cost of sending this person to city A vs city B is 10 – 20 = -30

[10, 50] – The cost of sending this person to city A vs city B is 10 – 20 = -40

Since we are subtracting cost(B) from cost(A), if the difference is low, it means it’s better to send this person to city A and when the difference is very high, we send them to city B. Now let’s say we have costs for a person as [400, 50]. The cost of sending this person to city A vs city B (cityA – cityB) is +$350!! We might as well send them to city B. So that’s what we will do.

We will sort the costs by the difference cost(A) – cost(B) from low to high. For the first N/2 people of this sorted list, we send them to city A and for the next N/2, we send them to city B.

Time Complexity: Sorting takes O(N log N), so this will be O(N log N) + O(N/2) + O (N/2). So the overall complexity is O(N log N).

Space complexity: If we are doing an in-place sort, then the space complexity will be O(1)

Code for the above solution:

def twoCitySchedCost(self, costs: List[List[int]]) -> int:

    minCost = 0
    N = len(costs)

    costs.sort(key = lambda x: x[0] - x[1])
    for i in range(N // 2):
        minCost += costs[i][0]

    for i in range(N // 2, N):    
        minCost += costs[i][1]

    return minCost

Testing:

You can test the following cases.

• Any given test case: [[10,20],[30,200],[400,50],[30,20]]
• Case where cost to city A is the same and vice versa: [[10,20],[10,20],[10,40],[10,50]]
• Case where cost(A) = cost(B): [[10,10],[200,200],[400,400],[30,30]]
• A random case mixed with the above two cases: [[20,10],[400,200],[100,400],[3,30], [3,30],[40,40]]

Hope you learnt how to solve the two city scheduling problem. Have a nice day!