Two City Scheduling

GREEDY · MEDIUM

The problem

A company is interviewing 2n people. Person i costs costs[i][0] dollars to fly to city A, or costs[i][1] dollars to fly to city B. Exactly n people must end up in each city. Return the minimum total cost of flying everyone so that split is respected.

Every assignment is a choice of which n of the 2n people fly to city A — everyone else flies to city B. The question is which n to pick.

Solution 1: Brute force — try every possible split

The most literal reading of the problem: enumerate every possible group of n people to send to city A (the rest automatically go to city B), total the cost for each grouping, and keep the minimum. This is correct by definition — it is exactly what “minimum cost over all valid assignments” means — but the number of groupings is C(2n, n), which grows combinatorially. It’s only implemented and animated here for a tiny 4-person example; it would never scale to real input sizes.

costs = [[10, 20], [30, 200], [400, 50], [30, 20]] — each bar is one person's cost under the current A/B assignment

Press Play or Step to begin.

Combination being tried · best cost so far

Step 0 / 8

The code

function combinations(arr, k) {
  const results = [];
  function backtrack(start, chosen) {
    if (chosen.length === k) { results.push(chosen.slice()); return; }
    for (let i = start; i < arr.length; i++) {
      chosen.push(arr[i]);
      backtrack(i + 1, chosen);
      chosen.pop();
    }
  }
  backtrack(0, []);
  return results;
}

function twoCityBruteForce(costs) {
  const total = costs.length;
  const n = total / 2;
  const indices = costs.map((_, i) => i);
  const groupsA = combinations(indices, n);

  let best = Infinity;
  for (const groupA of groupsA) {
    const setA = new Set(groupA);
    let cost = 0;
    for (let i = 0; i < total; i++) {
      cost += setA.has(i) ? costs[i][0] : costs[i][1];
    }
    best = Math.min(best, cost);
  }
  return best;
}

Line by line:

combinations(indices, n) generates every way to choose n indices out of 2n to represent “these people fly to city A” — there are C(2n, n) of them.
For each candidate group, setA.has(i) decides per person whether to charge costs[i][0] (city A) or costs[i][1] (city B) — everyone not chosen for A automatically goes to B, so the split is always exactly n and n.
best = Math.min(best, cost) just keeps the cheapest total seen across every group — no shortcuts, no pruning.

Complexity

Time	Space	Approach
O(C(2n, n) · n) — combinatorial	O(n)	Enumerate every valid A/B split, sum, keep the min

Solution 2: Optimal — greedy sort by savings

Reframe the decision: sending person i to city A instead of city B changes the cost by aCost − bCost. If that number is very negative, A is a big bargain for that person; if it’s very positive, B is the bargain. To minimize the total, greedily send the n people with the smallest aCost − bCost (the biggest savings from choosing A) to city A, and send the rest to city B. Sort once by that difference, ascending, and split the sorted array down the middle — no combinatorial search needed.

costs = [[10, 20], [30, 200], [400, 50], [30, 20]] · Bars show aCost − bCost for each person in sorted order

Press Play or Step to begin.

Current person · diff value · assignment · running total

Step 0 / 7

The code

function twoCityOptimal(costs) {
  const n = costs.length / 2;
  const sorted = costs.slice().sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));

  let total = 0;
  for (let i = 0; i < sorted.length; i++) {
    total += i < n ? sorted[i][0] : sorted[i][1];
  }
  return total;
}

Line by line:

costs.slice() copies the array first — sorting in place would silently reorder the caller’s original costs, which is rarely what’s wanted.
.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1])) orders people ascending by aCost − bCost: the biggest A-savings first, the biggest B-savings last.
i < n is the entire “decision” step — the first n people in sorted order fly to A, everyone after flies to B. Because the array is sorted by exactly the quantity that matters, this split is provably optimal — swapping any A/B pair across the boundary can only make the total equal or worse, never better.

Complexity

Time	Space	Approach
O(n log n)	O(n)	Sort by aCost − bCost, split the sorted array in half

Complexity comparison

Solution	Time	Space
Brute force (enumerate every split)	O(C(2n, n) · n) — combinatorial	O(n)
Optimal (greedy sort by savings)	O(n log n)	O(n)

Honest caveat: the brute-force code above is only ever run against the small 4-person example on this page. C(2n, n) already reaches 184,756 at 2n=20 and billions well before 2n=60 — it is not a “slow but usable” fallback, it is asymptotically infeasible for any realistic input size.

Interview corner

Why does sorting by aCost − bCost guarantee the optimal split, instead of just being a reasonable heuristic?

Every valid assignment sends exactly n people to A and n to B — the total cost is (sum of everyone’s bCost) + (sum of aCost − bCost for whoever was sent to A).
The first term is fixed no matter which n people are chosen, so minimizing the total means minimizing the sum of aCost − bCost over the chosen A-group.
To minimize a sum of n values picked out of 2n, pick the n smallest — which is exactly “sort ascending by diff, take the first n”. That’s a proof, not a guess.

What’s an exchange-argument way to convince an interviewer this greedy choice can’t be beaten?

Suppose an optimal solution sends person X to B and person Y to A, but X’s diff (aCost − bCost) is smaller than Y’s.
Swap them: send X to A and Y to B instead. The total cost changes by (X's diff) − (Y's diff), which is negative or zero since X’s diff is smaller — the swap never makes things worse, and strictly improves them if the diffs differ.
So any solution that isn’t sorted-by-diff can be transformed into one that is, without increasing cost — meaning the sorted split is always at least as good as any alternative.

How would you extend this if the two cities didn’t need exactly equal n/n splits — say, city A needs exactly k people for some given k?

The same proof still holds — it never depended on k being exactly half.
Sort by aCost − bCost ascending, send the first k to A, the remaining 2n − k to B.
The only real requirement is that k people go to A and the rest go to B — the greedy argument (swap any A/B pair sorted “wrong” without raising the total) applies unchanged.
↳ Common follow-up: “What if a person can only be sent to one specific city (a hard constraint)?” That breaks the simple sort — it becomes closer to an assignment/flow problem, since some people are no longer free to be greedily reassigned.

Trick question — what does this log?

const costs = [[10, 20], [30, 200], [400, 50], [30, 20]];
const sorted = costs.slice().sort();
console.log(sorted[0]);

Answer: [10, 20] — which happens to look plausible, but the whole array is now wrong: sorted is [[10,20],[30,20],[30,200],[400,50]], not sorted by diff at all.
.sort() with no comparator converts every element to a string and compares them lexicographically. [400, 50] becomes the string "400,50", which sorts before "30,20" — treating 4 as “less than” 3 is nonsense for numbers, but that’s how string comparison works.
It happens to put the actual answer first here purely by coincidence of these specific numbers — it is not doing anything close to sorting by aCost − bCost.
⚠ Trap: this is exactly why the real solution always passes an explicit comparator, (a, b) => (a[0] - a[1]) - (b[0] - b[1]) — leaving it off doesn’t throw an error, it silently produces a different (and here, wrong) order.

Quiz

1. Why does minimizing total cost reduce to minimizing the sum of (aCost − bCost) over just the people sent to city A?

Because the sum of everyone’s bCost is the same for every valid split, so only the A-group’s diff sum varies
Because aCost always equals bCost for half the people
It doesn’t reduce to that — the two are unrelated

2. Given the diff values are what matters, why does taking the SMALLEST n diffs (not the largest) minimize the total?

The sum of any n values out of 2n is minimized by choosing the n smallest of them
Larger diffs always mean cheaper flights
Which n values are chosen never changes the total

3. What’s the core exchange-argument idea that proves the greedy split is optimal, not just a good guess?

Swapping any A/B pair that’s out of sorted order never increases (and can only decrease) the total cost
It was checked against enough LeetCode examples to be confident
There’s no proof — it’s a heuristic that happens to score well

4. Why is the brute force fundamentally worse than “slow” — what makes it infeasible even for moderate n?

The number of groupings it checks, C(2n, n), grows combinatorially — not linearly or even polynomially
It’s only a small constant factor slower than the greedy solution
It has the same Big O as the greedy solution, just with worse constants

5. What’s the risk of writing costs.sort() instead of costs.sort((a, b) => (a[0]-a[1]) - (b[0]-b[1])) in this solution?

With no comparator, .sort() converts elements to strings and sorts lexicographically — silently the wrong order for this problem
It throws a TypeError immediately, so the bug is easy to catch
.sort() always falls back to numeric ascending order automatically