Skip to content

1029. Two City Scheduling

SourceWeekly Contest 133 Q1DifficultyMediumRating1348

Description

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.

 

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.

Example 2:

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

Example 3:

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

 

Constraints:

  • 2 * n == costs.length
  • 2 <= costs.length <= 100
  • costs.length is even.
  • 1 <= aCosti, bCosti <= 1000

Solutions

Solution 1

Thinking

Choosing which \(n\) of \(2n\) people fly to \(A\) is exponential if done by subsets. Sending everyone to \(B\) and then switching \(n\) people to \(A\) changes the cost by \(aCost-bCost\).

The people with the smallest (most negative) differences save the most when switched. Sorting by \(aCost-bCost\) and sending the first half to \(A\) and the rest to \(B\) is optimal.

The answer is the corresponding half-and-half sum.

1
2
3
4
5
class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda x: x[0] - x[1])
        n = len(costs) >> 1
        return sum(costs[i][0] + costs[i + n][1] for i in range(n))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, (a, b) -> { return a[0] - a[1] - (b[0] - b[1]); });
        int ans = 0;
        int n = costs.length >> 1;
        for (int i = 0; i < n; ++i) {
            ans += costs[i][0] + costs[i + n][1];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] - a[1] < b[0] - b[1];
        });
        int n = costs.size() / 2;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += costs[i][0] + costs[i + n][1];
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func twoCitySchedCost(costs [][]int) (ans int) {
    sort.Slice(costs, func(i, j int) bool {
        return costs[i][0]-costs[i][1] < costs[j][0]-costs[j][1]
    })
    n := len(costs) >> 1
    for i, a := range costs[:n] {
        ans += a[0] + costs[i+n][1]
    }
    return
}

1
2
3
4
5
6
7
8
9
function twoCitySchedCost(costs: number[][]): number {
    costs.sort((a, b) => a[0] - a[1] - (b[0] - b[1]));
    const n = costs.length >> 1;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        ans += costs[i][0] + costs[i + n][1];
    }
    return ans;
}

Comments