有
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
TIP
按「去 A 比去 B 省多少」排序，前 n 個去 A，後 n 個去 B。
- 假設所有人先去 B，總費用為
sum(bCost) - 將某人改去 A 的額外成本為
aCost - bCost - 選額外成本最小的 n 個人去 A
Approaches
1. Sort + Greedy — O(n log n) / O(1)
- Idea: 按
aCost - bCost排序，前 n 個去 A、後 n 個去 B。 - Time:
O(n log n) - Space:
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. As Above + Clearer Derivation — O(n log n) / O(n)
- Idea: 先假設所有人都去 B，然後計算改去 A 的「節省」，選節省最多的 n 個人改去 A。
- Time:
O(n log n) - Space:
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 的額外成本」排序
- Key trick: 先假設所有人去同一城市，再按差值排序選擇換人；這是分配問題的經典貪心策略