## Two City Scheduling

• Time:O(n\log n)
• Space:O(1)

## C++

``````class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
const int n = costs.size() / 2;
int ans = 0;

// How much money can we save if we fly a person to A instead of B?
// To save money, we should
//   1) fly the person with the max saving to A
//   2) fly the person with the min saving to B
sort(begin(costs), end(costs), [](const auto& a, const auto& b) {
// sort in descending order by the money saved
// if we fly a person to A instead of B
return a[1] - a[0] > b[1] - b[0];
});

for (int i = 0; i < n; ++i)
ans += costs[i][0] + costs[i + n][1];

return ans;
}
};
``````

## JAVA

``````class Solution {
public int twoCitySchedCost(int[][] costs) {
final int n = costs.length / 2;
int ans = 0;

// How much money can we save if we fly a person to A instead of B?
// To save money, we should
//   1) fly the person with the max saving to A
//   2) fly the person with the min saving to B

// sort in descending order by the money saved if we fly a person to A instead of B
Arrays.sort(costs, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));

for (int i = 0; i < n; ++i)
ans += costs[i][0] + costs[i + n][1];

return ans;
}
}
``````

## Python

``````class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
n = len(costs) // 2

# How much money can we save if we fly a person to A instead of B?
# To save money, we should
#   1) fly the person with the max saving to A
#   2) fly the person with the min saving to B

# sort in descending order by the money saved if we fly a person to A
costs.sort(key=lambda x: x[0] - x[1])
return sum(costs[i][0] + costs[i + n][1] for i in range(n))
``````