What is the main pattern behind Two City Scheduling?

It is a greedy choice plus invariant validation problem where sorting by cost difference allows optimal assignment.

How do you ensure exactly n people go to each city?

After sorting by cost difference, assign the first n people to city A and the rest to city B, preserving the n-per-city invariant.

Can this approach fail for large n?

The approach is efficient; sorting dominates time complexity as O(n log n), which scales well for n up to 50 (2n = 100).

Why not simply assign each person to their cheaper city?

Greedy assignment without considering the n-per-city constraint may overload one city and lead to higher total cost.

Does GhostInterview provide the final minimal cost?

Yes, it calculates the cost differences, applies the greedy assignment, and returns the exact minimum total travel cost.

#1029

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

两地调度

公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCost i , bCost i ] 。第 i 人飞往 a 市的费用为 aCost i ，飞往 b 市的费用为 bCost i 。返回将每个人都飞到 a 、 b 中某座城市的最低费用，要求每个城市都有 n 人抵达 …

数组贪心排序

题目描述

公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCost_i, bCost_i] 。第 i 人飞往 a 市的费用为 aCost_i ，飞往 b 市的费用为 bCost_i 。

返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。

示例 1：

输入：costs = [[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 a 市，费用为 10。
第二个人去 a 市，费用为 30。
第三个人去 b 市，费用为 50。
第四个人去 b 市，费用为 20。

最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

示例 2：

输入：costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
输出：1859

示例 3：

输入：costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
输出：3086

提示：

2 * n == costs.length
2 <= costs.length <= 100
costs.length 为偶数
1 <= aCost_i, bCost_i <= 1000

lightbulb

解题思路

方法一：排序 + 贪心

我们不妨先假设所有人都去 $b$ 市，然后我们要从中选出 $n$ 个人去 $a$ 市，使得总费用最小。如果一个人去 $a$ 市的费用比去 $b$ 市的费用小，我们把这个人从 $b$ 市调到 $a$ 市，这样总费用就会减少。因此，我们可以将所有人按照去 $a$ 市的费用与去 $b$ 市的费用的差值从小到大排序，然后选出前 $n$ 个人去 $a$ 市，剩下的人去 $b$ 市，这样总费用就是最小的。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 costs 的长度。

相似题目：

2611. 老鼠和奶酪

1

2

3

4

5

6

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

speed

复杂度分析

指标	值
时间	complexity is dominated by the sorting step, O(n log n), and space complexity is O(n) for storing differences and sorting indexes.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate considers individual cost differences and recognizes sorting as a key step.
question_mark
Candidate validates that exactly n people are assigned per city to avoid constraint violations.
question_mark
Candidate can explain why the greedy assignment leads to a globally minimal cost rather than just a local choice.

warning

常见陷阱

外企场景

error
Failing to maintain exactly n people per city after sorting, which violates problem constraints.
error
Sorting by absolute cost instead of the cost difference, leading to suboptimal total cost.
error
Overlooking edge cases where multiple people have identical cost differences, potentially affecting assignment order.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Assigning people to three cities instead of two with the same minimal cost goal.
arrow_right_alt
Considering additional constraints like flight availability or maximum individual cost per person.
arrow_right_alt
Handling large input sizes where sorting efficiency becomes critical and alternative data structures may help.

help

常见问题

外企场景

继续练习

#1005 K 次取反后最大化的数组和 #1054 距离相等的条形码 #976 三角形的最大周长