# 1029. Two City Scheduling

## 題目敘述

A company is planning to interview `2n` people. Given the array `costs` where `costs[i] = [aCosti, bCosti]`, the cost of flying the `i**th` person to city `a` is `aCosti`, and the cost of flying the `i**th` 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`

## 解法解析

### 解法範例

#### Go

``````func twoCitySchedCost(costs [][]int) int {
sort.Slice(costs, func(i, j int) bool {
return costs[i][0]-costs[i][1] < costs[j][0]-costs[j][1]
})
var total int
n := len(costs) / 2
for i := 0; i < n; i++ {
total += costs[i][0] + costs[i+n][1]
}
}
``````

#### JavaScript

``````/**
* @param {number[][]} costs
* @return {number}
*/
var twoCitySchedCost = function (costs) {
costs.sort((a, b) => a[0] - a[1] - (b[0] - b[1]));
let total = 0;
const n = costs.length / 2;
for (let i = 0; i < n; i++) {
total += costs[i][0] + costs[i + n][1];
}
};
``````

#### Kotlin

``````class Solution {
fun twoCitySchedCost(costs: Array<IntArray>): Int {
costs.sortWith(compareBy { it[0] - it[1] })

val n = costs.size / 2
return costsByDiffs.withIndex().sumBy {
it.value[ if (it.index < n) 0 else 1 ]
}
}
}
``````

#### PHP

``````class Solution
{

/**
* @param Integer[][] \$costs
* @return Integer
*/
function twoCitySchedCost(\$costs)
{
usort(\$costs, function (\$a, \$b) {
return (\$a[0] - \$a[1]) - (\$b[0] - \$b[1]);
});

\$total = 0;
\$n = count(\$costs) / 2;
for (\$i = 0; \$i < \$n; \$i++) {
\$total += \$costs[\$i][0] + \$costs[\$i + \$n][1];
}
return \$total;
}
}
``````

#### Python

``````class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
# Sort by a gain which company has
# by sending a person to city A and not to city B
costs.sort(key=lambda x: x[0] - x[1])

total = 0
n = len(costs) // 2
# To optimize the company expenses,
# send the first n persons to the city A
# and the others to the city B
for i in range(n):
total += costs[i][0] + costs[i + n][1]
``````

#### Rust

``````impl Solution {
pub fn two_city_sched_cost(costs: Vec<Vec<i32>>) -> i32 {
let mut costs = costs;
costs.sort_by(|a, b| (a[0] - a[1]).cmp(&(b[0] - b[1])));
let mut total = 0;
let n: usize = costs.len() / 2;
for i in 0..n {
total += costs[i][0] + costs[i + n][1];
}
total
}
}
``````

#### Swift

``````class Solution {
func twoCitySchedCost(_ costs: [[Int]]) -> Int {
var costs = costs
costs.sort { \$0[0] - \$0[1] < \$1[0] - \$1[1] }
var total = 0
let n = costs.count / 2
for i in 0..<n {
total += costs[i][0] + costs[i + n][1]
}