1029.md

1029. Two City Scheduling

Leetcode link

解题思路

题目叫我们把一半的人安排到 a 市，一半的人安排到 b 市，那我们可以针对去 a 市的成本 aCost 与去 b 市的成本 bCost 求差值之后升序排序来确定去 a 市的名单，剩下的一半则是去 b 市的名单。

使用 aCost - bCost 之后由小到大排序是因为当去 a 市的成本与去 b 市的成本少的越多（差值越大）很显然我们应该优先安排该候选人去 a 市（机会成本更小一点）

C++

bool comparator(vector<int> &a, vector<int> &b) {
  if (a[0] - a[1] < b[0] - b[1]) {
    return true;
  } else {
    return false;
  }
}

class Solution {
 public:
  int twoCitySchedCost(vector<vector<int>> &costs) {
    // 排序
    sort(costs.begin(), costs.end(), comparator);
    int result = 0, n = costs.size() / 2;
    // 只遍历一半的 vector，前面的一半去 a 市，后面的一半去 b 市
    for (int i = 0; i < n; i++) {
      result += costs[i][0] + costs[n + i][1];
    }
    return result;
  }
};

Javascript

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