Two City Scheduling

Problem

2n candidates can interview at one of two cities. costs[i] = [costA, costB]. Send exactly n to each city to minimise total cost.

Constraints

• 2 ≤ costs.length ≤ 100
• costs.length is even

Approach — Greedy

This is a Greedy problem. The idea: make the locally best choice at each step, which provably builds up to the global optimum here. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log n) time.

Solution code

Python

class Solution:
    def twoCitySchedCost(self, costs):
        costs.sort(key=lambda c: c[0] - c[1])
        n = len(costs) // 2
        return sum(c[0] for c in costs[:n]) + sum(c[1] for c in costs[n:])

Java

import java.util.*;

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.