公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [, ] 。第 i 人飞往 a 市的费用为  ，飞往 b 市的费用为  。

返回将每个人都飞到 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.length
• 2 <= costs.length <= 100
• costs.length 为偶数
• 1 <= ,  <= 1000

---

贪心算法，更多的考验转换问题的能力，与其让2n人从全国各地出发，不如让2n人全在A地，那么问题就转化成：从这2n个人中挑选n个前往B地，挑选条件是，他们的 - 最小。

考虑这种转换的正确性：

• bCost-aCost表示这个人去A地和B地的价格差。也即这个人去B不去A能产生的收益。
• 这个结果有正有负，负的当然代表这个人去B地更便宜。
• 而我们安排bCost - aCost最小的n个人去B地，即使这个值是正的，也是最小的正数，也即多花费的最小额。而负数越小说明省的越多。

class Solution {
public:int twoCitySchedCost(vector<vector<int>>& costs) {sort(costs.begin(),costs.end(),[](auto& a,auto&b){return a[0] - a[1] < b[0] - b[1];});int result = 0;for(int i = 0 ;i < costs.size() / 2;++i){result += costs[i][0] + costs[i+costs.size()/2][1];}return result;}
};