1
/**
2
 * @param {number[][]} costs
3
 * @return {number}
4
 */
5
var twoCitySchedCost = function (costs) {
6
  // TC: O(nlogn) and O(1) extra space
7
  let n = costs.length;
8
  let countA = 0,
9
    countB = 0,
10
    minCost = 0;
11

12
  // sorted in descending order by their absolute diff
13
  costs = costs.sort((a, b) => {
14
    let diffA = Math.abs(a[0] - a[1]);
15
    let diffB = Math.abs(b[0] - b[1]);
16
    return diffB - diffA;
17
  });
18

19
  for (let i = 0; i < n; i++) {
20
    let [a, b] = costs[i];
21
    if (a < b) {
22
      if (countA < n / 2) {
23
        minCost += a;
24
        countA++;
25
      } else {
26
        minCost += b;
27
        countB++;
28
      }
29
    } else {
30
      if (countB < n / 2) {
31
        minCost += b;
32
        countB++;
33
      } else {
34
        minCost += a;
35
        countA++;
36
      }
37
    }
38
  }
39
  return minCost;
40
};