Two City Scheduling

medium array greedy sorting

Problem

Given 2n people where costs[i] = [costA, costB] (the cost to fly person i to city A or city B), return the minimum total cost when exactly n people go to each city.

Inputcosts = [[10,20],[30,200],[400,50],[30,20]]

Output110

Sort by (A − B). Send the 2 cheapest-A-relatively to A, others to B.

costs (semicolon-separated 'A,B' pairs, length must be even)

def two_city_sched_cost(costs):
    costs.sort(key=lambda c: c[0] - c[1])
    n = len(costs) // 2
    total = 0
    for i, (a, b) in enumerate(costs):
        total += a if i < n else b
    return total

function twoCitySchedCost(costs) {
  costs.sort((x, y) => (x[0] - x[1]) - (y[0] - y[1]));
  const n = costs.length / 2;
  let total = 0;
  for (let i = 0; i < costs.length; i++) {
    total += i < n ? costs[i][0] : costs[i][1];
  }
  return total;
}

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, (x, y) -> (x[0] - x[1]) - (y[0] - y[1]));
        int n = costs.length / 2, total = 0;
        for (int i = 0; i < costs.length; i++) {
            total += i < n ? costs[i][0] : costs[i][1];
        }
        return total;
    }
}

int twoCitySchedCost(vector<vector<int>>& costs) {
    sort(costs.begin(), costs.end(), [](auto& x, auto& y) {
        return (x[0] - x[1]) < (y[0] - y[1]);
    });
    int n = costs.size() / 2, total = 0;
    for (int i = 0; i < (int)costs.size(); i++) {
        total += i < n ? costs[i][0] : costs[i][1];
    }
    return total;
}

Explanation

We must send exactly half the people to city A and half to city B at the lowest total cost. The key idea is a greedy sort by how much cheaper A is than B for each person.

For person i the value cost_A - cost_B tells us their "preference": a very negative number means A is a big bargain for them, a large positive number means B is the bargain.

So we sort everyone by cost_A - cost_B ascending. The first n people (most eager for A) go to city A, and the remaining n go to city B. We just add up a for the first half and b for the second half.

Example: [[10,20],[30,200],[400,50],[30,20]]. Differences are -10, -170, 350, 10. Sorted, the two most negative go to A and the rest to B, giving a minimum total of 110.

It works because swapping any A-person with any B-person would only ever raise the total — the sort already paired each person with their cheaper relative side.

Time: O(n log n) Space: O(1)