Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

two-city-scheduling.js

export function twoCityScheduling(costs) {
  // create an array of cost differences and sort it ascending
  const diffs = costs.map(([costA, costB]) => costA - costB);
  diffs.sort((a, b) => a - b);

  // get a sum of all costs to city A (like we sent all people to city A)
  let sumA = costs.reduce((sum, [costA]) => sum + costA, 0);

  // since we are actually sending the second half of people (by diffs) to city B
  // subtract their differences (think refunds) from the sumA
  for (let i = diffs.length / 2; i < diffs.length; ++i) {
    sumA -= diffs[i];
  }

  return sumA;
}

// O(n + nlogn) because of sorting, O(n + m) memory (m because of sorting).