1029. Two City Scheduling

Medium
Description

有 2n 個人要分成兩組，分別飛往城市 A 和城市 B，每組恰好 n 人。costs[i] = [aCost_i, bCost_i] 表示第 i 個人飛往 A 和 B 的費用。回傳最小總費用。

Example:

Input: costs = [[10,20],[30,200],[400,50],[30,20]] Output: 110

Intuition#

按「去 A 比去 B 省多少」排序，前 n 個去 A，後 n 個去 B。

  • 假設所有人先去 B，總費用為 sum(bCost)
  • 將某人改去 A 的額外成本為 aCost - bCost
  • 選額外成本最小的 n 個人去 A

Approaches#

1: 排序 + 貪心#

  • 概念: 按 aCost - bCost 排序，前 n 個去 A、後 n 個去 B。
  • 時間複雜度: O(n log n)
  • 空間複雜度: O(1)（排序為原地）
class Solution {
    fun twoCitySchedCost(costs: Array<IntArray>): Int {
        costs.sortBy { it[0] - it[1] }
        val n = costs.size / 2
        var total = 0
        for (i in costs.indices) {
            total += if (i < n) costs[i][0] else costs[i][1]
        }
        return total
    }
}

⭐2: 同上 + 更清晰的推導#

  • 概念: 先假設所有人都去 B，然後計算改去 A 的「節省」，選節省最多的 n 個人改去 A。
  • 時間複雜度: O(n log n)
  • 空間複雜度: O(n)
class Solution {
    fun twoCitySchedCost(costs: Array<IntArray>): Int {
        val n = costs.size / 2
        var totalB = 0
        val diff = IntArray(costs.size)

        for (i in costs.indices) {
            totalB += costs[i][1]
            diff[i] = costs[i][0] - costs[i][1] // 改去 A 的額外成本
        }
        diff.sort()

        // 選額外成本最小（最負 = 節省最多）的 n 人改去 A
        var result = totalB
        for (i in 0 until n) {
            result += diff[i]
        }
        return result
    }
}

🔑 Takeaways#

  • Pattern: 差值排序貪心 — 按「選 A 比選 B 的額外成本」排序
  • 關鍵技巧: 先假設所有人去同一城市，再按差值排序選擇換人；這是分配問題的經典貪心策略