Two City Scheduling

Problem

A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.

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

Examples

Example 1:

1
2
3
4
5
6
7
8
9


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.

Example 2:

1
2


Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859

Example 3:

1
2


Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
Output: 3086

Solution

First example is kind of misleading, as we take min of city A and B, then each person is going to respective city. We are interested in overall min cost for the company, and half of people should go to A and half to B.

So, 1 solution is backtracking as a brute force solution. And as we want min cost, then DP can also help, but there is a greedy solution as well.

Method 1 - Greedy Using Cost Difference

Lets assume we send all persons to city A.

The idea is to send each person to city A.

1

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

So, totalCost = 10 + 30 + 400 + 30 = 470

Now, we need to send n persons to city B. Which persons do we need to send city B?

Here, we need to minimize the cost.

Now, we have already paid money to go to city A. So, Send the persons to city B who get more refund so that our cost will be minimized.

So, maintain refunds of each person,

1

refund[i] = cost[i][1] - cost[i][0]

So, refunds of each person

1

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

Here, refund +ve means we need to pay, -ve means we will get refund.

So, sort the refund array.

1

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

Now, get refund for N persons,

1

totalCost += 470 + -350 + -10 = 110

So, minimum cost is 110

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
	public int twoCitySchedCost(int[][] costs) {
		int N = costs.length/2;
		int[] refund = new int[N * 2];
		int minCost = 0, index = 0;
		for(int[] cost : costs){
			refund[index++] = cost[1] - cost[0];
			minCost += cost[0];
		}
		Arrays.sort(refund);
		for(int i = 0; i < N; i++){
			minCost += refund[i];
		}
		return minCost;
	}
}

Complexity

⏰ Time complexity: O(n log n)
- O(n) to compute the initial cost and refund array.
- O(n log n) to sort the refund array.
- O(n) to sum the N smallest refunds.
- Overall: O(n log n) (sorting dominates).
🧺 Space complexity: O(n)
- O(n) for the refund array.
- O(1) extra space otherwise (ignoring input and output).

Problem#

Examples#

Solution#

Method 1 - Greedy Using Cost Difference#

Code#

Complexity#