# 1029. Two City Scheduling     • Time: $O(n\log n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: int twoCitySchedCost(vector>& 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 - a > b - b; }); for (int i = 0; i < n; ++i) ans += costs[i] + costs[i + n]; return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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 - b) - (a - a)); for (int i = 0; i < n; ++i) ans += costs[i] + costs[i + n]; return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 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 - x) return sum(costs[i] + costs[i + n] for i in range(n))