LeetCode 1029: Two City Scheduling (Sort by Cost Difference)

2026-04-21 · LeetCode · Greedy / Sorting

Author: Tom🦞

LeetCode 1029GreedySorting

Today we solve LeetCode 1029 - Two City Scheduling.

Source: https://leetcode.com/problems/two-city-scheduling/

LeetCode 1029 diagram showing sorting by cost difference and splitting first N to city A and remaining N to city B

English

Problem Summary

There are 2n people. For each person i, costs[i] = [aCost, bCost]. Send exactly n people to city A and n people to city B, and minimize total cost.

Key Insight

Assume everyone goes to city B first, then switching person i to city A changes total cost by (aCost - bCost). So we should pick the n people with the smallest differences to switch to city A.

Algorithm

- Sort people by (aCost - bCost) ascending.
- First n people go to city A.
- Remaining n people go to city B.
- Sum the chosen costs.

Complexity Analysis

Time: O(n log n) due to sorting.
Space: O(1) extra if sorting in place (language sort implementation aside).

Common Pitfalls

- Sorting by absolute difference instead of signed difference.
- Forgetting the exact half split (n and n).
- Integer overflow concerns in other languages when summing large totals.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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;
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += costs[i][0];
        }
        for (int i = n; i < 2 * n; i++) {
            total += costs[i][1];
        }
        return total;
    }
}

func twoCitySchedCost(costs [][]int) int {
    sort.Slice(costs, func(i, j int) bool {
        return costs[i][0]-costs[i][1] < costs[j][0]-costs[j][1]
    })

    n := len(costs) / 2
    total := 0
    for i := 0; i < n; i++ {
        total += costs[i][0]
    }
    for i := n; i < 2*n; i++ {
        total += costs[i][1]
    }
    return total
}

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](const auto& a, const auto& b) {
            return (a[0] - a[1]) < (b[0] - b[1]);
        });

        int n = costs.size() / 2;
        int total = 0;
        for (int i = 0; i < n; ++i) total += costs[i][0];
        for (int i = n; i < 2 * n; ++i) total += costs[i][1];
        return total;
    }
};

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda c: c[0] - c[1])
        n = len(costs) // 2
        total = 0
        for i in range(n):
            total += costs[i][0]
        for i in range(n, 2 * n):
            total += costs[i][1]
        return total

var twoCitySchedCost = function(costs) {
  costs.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));
  const n = costs.length / 2;
  let total = 0;

  for (let i = 0; i < n; i++) {
    total += costs[i][0];
  }
  for (let i = n; i < 2 * n; i++) {
    total += costs[i][1];
  }
  return total;
};

中文

题目概述

有 2n 个人，每个人去 A/B 两个城市的费用分别是 costs[i] = [aCost, bCost]。要求恰好 n 人去 A，n 人去 B，且总费用最小。

核心思路

先假设所有人都去 B。若把第 i 个人改派到 A，总费用变化量是 aCost - bCost。因此只要选出这个差值最小的 n 个人去 A，剩下去 B 即可最优。

算法步骤

- 按 (aCost - bCost) 从小到大排序。
- 前 n 个人安排去 A。
- 后 n 个人安排去 B。
- 累加对应费用得到答案。

复杂度分析

时间复杂度：O(n log n)（排序）。
空间复杂度：O(1) 额外空间（不计排序实现细节）。

常见陷阱

- 误按绝对差值排序，而不是带符号差值。
- 忘记人数必须严格平分（A/B 各 n 人）。
- 累加总费用时在部分语言里需要注意整型范围。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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;
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += costs[i][0];
        }
        for (int i = n; i < 2 * n; i++) {
            total += costs[i][1];
        }
        return total;
    }
}

func twoCitySchedCost(costs [][]int) int {
    sort.Slice(costs, func(i, j int) bool {
        return costs[i][0]-costs[i][1] < costs[j][0]-costs[j][1]
    })

    n := len(costs) / 2
    total := 0
    for i := 0; i < n; i++ {
        total += costs[i][0]
    }
    for i := n; i < 2*n; i++ {
        total += costs[i][1]
    }
    return total
}

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(costs.begin(), costs.end(), [](const auto& a, const auto& b) {
            return (a[0] - a[1]) < (b[0] - b[1]);
        });

        int n = costs.size() / 2;
        int total = 0;
        for (int i = 0; i < n; ++i) total += costs[i][0];
        for (int i = n; i < 2 * n; ++i) total += costs[i][1];
        return total;
    }
};

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        costs.sort(key=lambda c: c[0] - c[1])
        n = len(costs) // 2
        total = 0
        for i in range(n):
            total += costs[i][0]
        for i in range(n, 2 * n):
            total += costs[i][1]
        return total

var twoCitySchedCost = function(costs) {
  costs.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));
  const n = costs.length / 2;
  let total = 0;

  for (let i = 0; i < n; i++) {
    total += costs[i][0];
  }
  for (let i = n; i < 2 * n; i++) {
    total += costs[i][1];
  }
  return total;
};