In this guide, you will get 1029. Two City Scheduling LeetCode Solution with the best time and space complexity. The solution to Two City Scheduling problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
1029. Two City Scheduling LeetCode Solution in 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 maximum saving to A.
// 2. Fly the person with the minimum saving to B.
// Sort `costs` in ascending order by the money saved if we fly a person to
// B instead of A.
ranges::sort(costs, ranges::less{},
[](const vector<int>& cost) { return cost[0] - cost[1]; });
for (int i = 0; i < n; ++i)
ans += costs[i][0] + costs[i + n][1];
return ans;
}
}; /* code provided by PROGIEZ */
1029. Two City Scheduling LeetCode Solution in 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 maximum saving to A.
// 2. Fly the person with the minimum saving to B.
// Sort `costs` in ascending order by the money saved if we fly a person to
// B instead of A.
Arrays.sort(costs, (a, b) -> Integer.compare(a[0] - a[1], b[0] - b[1]));
for (int i = 0; i < n; ++i)
ans += costs[i][0] + costs[i + n][1];
return ans;
}
} // code provided by PROGIEZ
1029. Two City Scheduling LeetCode Solution in 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 maximum saving to A.
# 2. Fly the person with the minimum saving to B.
# Sort `costs` in ascending order by the money saved if we fly a person to
# B instead of A.
costs.sort(key=lambda x: x[0] - x[1])
return sum(costs[i][0] + costs[i + n][1] for i in range(n)) # code by PROGIEZ
