class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
}
};
1029. 两地调度
公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。
返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。
示例 1：
输入：costs = [[10,20],[30,200],[400,50],[30,20]] 输出：110 解释： 第一个人去 a 市，费用为 10。 第二个人去 a 市，费用为 30。 第三个人去 b 市，费用为 50。 第四个人去 b 市，费用为 20。 最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。
示例 2：
输入：costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] 输出：1859
示例 3：
输入：costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]] 输出：3086
提示：
2 * n == costs.length2 <= costs.length <= 100costs.length 为偶数1 <= aCosti, bCosti <= 1000原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.4 MB, 提交时间: 2022-11-26 17:47:59
func twoCitySchedCost(costs [][]int) (res int) {
sort.Slice(costs, func(i, j int)bool{
return (costs[i][0] - costs[i][1]) < (costs[j][0] - costs[j][1])
})
for i := 0; i < len(costs) / 2; i++{
res += costs[i][0]
}
for i := len(costs) / 2; i < len(costs); i++{
res += costs[i][1]
}
return
}
java 解法, 执行用时: 1 ms, 内存消耗: 39.7 MB, 提交时间: 2022-11-26 17:47:18
class Solution {
public int twoCitySchedCost(int[][] costs) {
// Sort by a gain which company has
// by sending a person to city A and not to city B
Arrays.sort(costs, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o1[1] - (o2[0] - o2[1]);
}
});
int total = 0;
int n = costs.length / 2;
// To optimize the company expenses,
// send the first n persons to the city A
// and the others to the city B
for (int i = 0; i < n; ++i) total += costs[i][0] + costs[i + n][1];
return total;
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 15 MB, 提交时间: 2022-11-26 17:45:55
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]
return total