# 1029. Two City Scheduling

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.length`
• `2 <= costs.length <= 100`
• `costs.length` is even.
• `1 <= aCosti, bCosti <= 1000`

``````class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
int res = 0, n = costs.size() / 2;
vector<int> refund;
for (auto &cost : costs) {
res += cost[0];
refund.push_back(cost[1] - cost[0]);
}
sort(refund.begin(), refund.end());
for (int i = 0; i < n; ++i) {
res += refund[i];
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1029

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

https://leetcode.com/problems/two-city-scheduling/discuss/278716/C%2B%2B-O(n-log-n)-sort-by-savings

https://leetcode.com/problems/two-city-scheduling/discuss/667786/Java-or-C%2B%2B-or-Python3-or-With-detailed-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation