Last Updated on 2022-03-25 by Clay
題目
A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.
Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.
Example 1:
Input: costs = [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20. The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
Example 2:
Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] Output: 1859
Example 3:
Input: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]] Output: 3086
Constraints:
2 * n == costs.length2 <= costs.length <= 100costs.lengthis even.1 <= aCosti, bCosti <= 1000
我們會得到一個列表，列表中的每個元素代表一位面試者前往城市 A 跟城市 B 的成本（cost）。我們需要返回最小的成本並剛好讓城市 A 跟城市 B 的面試者人數相同。
解題思路
這題其實很直覺地 Greedy 解就能很順利地解出來了。一開始我寫了個照直覺的解法、後來又看到一個效能更好的解法。
以下，我把兩種解法都記錄了下來。
Greedy 解法
遍歷列表，並選成本最少的元素加入累積成本的變數，同時紀錄起前去的城市、以及變更為另一個城市的成本改變值（A 跟 B 分別計算）。
接著計算城市 A 跟 B 之間相差的人數，將人數除以二（因為一座城市增加一位面試者、另一座城市就會少掉一位面試者），接著端看哪座城市需要補人，按照最小的變更成本改變面試者的面試城市。
Greedy 複雜度
由於要找到最小的變更成本需要經歷排序，故時間複雜度一定為 O(nlog(n))。
而且由於我們需要儲存每個面試者變更城市的變更成本，故空間複雜度也是 O(n)。
| Time complexity | O(nlog(n)) |
| Space complexity | O(n) |
Greedy 解法 C++ 範例程式碼
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
// Init
int a = 0;
int b = 0;
int total = 0;
vector<int> aDiff;
vector<int> bDiff;
// Compute distances of city a and b; then greedy to determine where they go
for (auto& cost: costs) {
if (cost[0] < cost[1]) {
++a;
total += cost[0];
aDiff.push_back(cost[1]-cost[0]);
}
else {
++b;
total += cost[1];
bDiff.push_back(cost[0]-cost[1]);
}
}
// Sort
sort(aDiff.begin(), aDiff.end());
sort(bDiff.begin(), bDiff.end());
// Balance
if (a < b) {
int diff = (b - a) / 2;
for (int i=0; i<diff; ++i) {
total += bDiff[i];
}
}
else if (b < a) {
int diff = (a - b) / 2;
for (int i=0; i<diff; ++i) {
total += aDiff[i];
}
}
return total;
}
};Greedy 解法 Python 範例程式碼
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
# Init
a = 0
b = 0
total = 0
a_diff = []
b_diff = []
# Compute distances of city A and B; then greedy to determine where they go
for cost in costs:
if cost[0] < cost[1]:
a += 1
total += cost[0]
a_diff.append(cost[1]-cost[0])
else:
b += 1
total += cost[1]
b_diff.append(cost[0]-cost[1])
# Sort
a_diff.sort()
b_diff.sort()
# Balance
if a < b:
diff = (b - a) // 2
for i in range(diff):
total += b_diff[i]
elif b < a:
diff = (a - b) // 2
for i in range(diff):
total += a_diff[i]
return total
Greedy 解法（優化版）
不過原先的程式碼太冗長了。其實我們可以在一開始就假設所有的面試者都去城市 A，並直接把城市 A 跟城市 B 的變更成本紀錄起來、以及當前全部人去城市 A 的累積總成本。
接著，我們只需要計算出要讓幾位面試者去城市 B，並按照最小的變更消耗改變累積總成本，就可以得出最終值了。
這個解法的速度比較快，也不用另外計算有多少人去了城市 A 或 B，可說是徹底的優化寫法。
Greedy 複雜度（優化版）
由於我們還是要用排序來找到最小的變更成本，故時間複雜度依然為 O(nlog(n))。
而且由於我們還是需要儲存每個面試者變更城市的變更成本，故空間複雜度也是 O(n)。
| Time complexity | O(nlog(n)) |
| Space complexity | O(n) |
Greedy 解法 C++ 範例程式碼
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
// Init
int total = 0;
vector<int> diff;
// All people go to city A
for (auto& cost: costs) {
total += cost[0];
diff.push_back(cost[1]-cost[0]);
}
// Sort
sort(diff.begin(), diff.end());
// Balance
for (int i=0; i<costs.size()/2; ++i) {
total += diff[i];
}
return total;
}
};Greedy 解法 Python 範例程式碼
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
# Init
total = 0
diff = []
# All people go to city A
for cost in costs:
total += cost[0]
diff.append(cost[1]-cost[0])
# Sort
diff.sort()
# Balance
for i in range(len(costs)//2):
total += diff[i]
return total