Two City Scheduling solution and explanation
Google
9 more videos on this problem
Two City Scheduling - Leetcode 1029 - PythonNeetCode · 11:34 · 32K views
Two City Scheduling | Leetcode #1029Techdose · 9:35 · 22K views
two city scheduling | two city scheduling leetcode | leetcode 1029thecodingworld · 7:43 · 6K views
Two City Scheduling | LeetCode 1029 | C++, Java, PythonKnowledge Center · 14:43 · 6K views
Two City Scheduling | Leetcode 1029 | Greedy | Sorting | Day-25Ayushi Sharma · 18:23 · 3K views
Two City Scheduling - LeetCode 1029Michael Vandi · 13:44 · 2K views
Two city Scheduling Solution | Leetcode #1029 | C++ | Code + ExplanationCode with Alisha · 7:26 · 1K views
Two City Scheduling | Leetcode 1029 | Greedy | Live coding session 🔥🔥Coding Decoded · 8:13 · 1K views
Two City Scheduling - LeetCode (Solution & Explanation | JavaScript)shirin setayesh · 10:11 · 1K views
Two City Scheduling || leetcode 1029 || greedy solution || c++ solutioncode Explainer · 7:38 · 904 views
The problem
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
Approach overview
Problem Overview: You are given 2n people and the cost of flying each person to city A or city B. Exactly n people must go to each city. The goal is to minimize the total travel cost.
Approach 1: Brute Force Assignment (Exponential Time)
The most direct idea is to try every valid assignment where exactly half of the people go to city A and the rest go to city B. For each person you choose either city, track the number already assigned to each city, and compute the total cost. This can be implemented using recursion or backtracking. The approach explores all valid combinations and keeps the minimum total cost.
This method quickly becomes infeasible because the number of combinations grows exponentially. With 2n people, the number of valid assignments is roughly C(2n, n). Time complexity is O(2^n) in practice, and space complexity is O(n) due to recursion depth. It helps build intuition but is not practical for large inputs.
Approach 2: Greedy Approach with Sorting (O(n log n))
The optimal strategy relies on the difference between sending a person to city A versus city B. For each person compute costA - costB. This value tells you how much cheaper (or more expensive) city A is compared to city B. If the difference is very negative, sending that person to A saves a lot of money. If it is very positive, city B is cheaper.
Sort the people based on this difference. After sorting, send the first n people (those who benefit most from going to A) to city A, and the remaining n people to city B. Sorting guarantees the largest savings decisions happen first. The final cost is simply the sum of the chosen city cost for each person.
This greedy rule works because each decision is based on relative savings, which remains optimal after sorting. The algorithm performs one sort and one pass through the array. Time complexity is O(n log n) due to sorting, and space complexity is O(1) if sorting is in-place.
This problem is a classic example of combining Greedy decision making with Sorting to optimize assignments in an Array-based problem.
Recommended for interviews: The greedy sorting approach is what interviewers expect. Mentioning the brute force idea shows you understand the constraints of the problem space, but implementing the difference-based sorting demonstrates strong algorithmic intuition and the ability to recognize greedy optimization patterns.
Approach 1: Greedy Approach with Sorting
This approach relies on sorting the people by the difference between the cost of flying them to city A and city B. By doing so, we can initially assume that flying every person to city A is optimal, and then we adjust half of the people to go to city B based on minimal added cost.
def twoCitySchedCost(costs):
costs.sort(key=lambda cost: cost[0] - cost[1])
n = len(costs) // 2
totalCost = sum(cost[0] for cost in costs[:n]) + sum(cost[1] for cost in costs[n:])
return totalCostimport java.util.*;
class Solution {
public int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
int n = costs.length / 2;
int totalCost = 0;
for (int i = 0; i < n; i++) {
totalCost += costs[i][0] + costs[i+n][1];
}
return totalCost;
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int twoCitySchedCost(vector<vector<int>>& costs) {
sort(costs.begin(), costs.end(), [](const vector<int>& a, const vector<int>& b) {
return (a[0] - a[1]) < (b[0] - b[1]);
});
int n = costs.size() / 2;
int totalCost = 0;
for (int i = 0; i < n; ++i) {
totalCost += costs[i][0] + costs[i + n][1];
}
return totalCost;
}var twoCitySchedCost = function(costs) {
costs.sort((a, b) => (a[0] - a[1]) - (b[0] - b[1]));
let totalCost = 0;
for (let i = 0; i < costs.length / 2; i++) {
totalCost += costs[i][0] + costs[i + costs.length / 2][1];
}
return totalCost;
};#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
int *cost1 = *(int **)a;
int *cost2 = *(int **)b;
return (cost1[0] - cost1[1]) - (cost2[0] - cost2[1]);
}
int twoCitySchedCost(int** costs, int costsSize, int* costsColSize) {
qsort(costs, costsSize, sizeof(int*), compare);
int totalCost = 0;
for (int i = 0; i < costsSize / 2; i++) {
totalCost += costs[i][0] + costs[i + costsSize / 2][1];
}
return totalCost;
}using System;
using System.Collections.Generic;
public class Solution {
public int TwoCitySchedCost(int[][] costs) {
Array.Sort(costs, (a, b) => (a[0] - a[1]) - (b[0] - b[1]));
int totalCost = 0;
int n = costs.Length / 2;
for (int i = 0; i < n; i++) {
totalCost += costs[i][0] + costs[i + n][1];
}
return totalCost;
}
}Python's solution sorts the list using the custom key which is the cost difference between city A and city B. The total cost is then computed by summing the cheaper city for the suitable half of the sorted list.
The time complexity of this algorithm is O(n log n) due to the sorting mechanism and the space complexity is O(1).
Approach 2: Default Approach
function twoCitySchedCost(costs: number[][]): number {
costs.sort((a, b) => a[0] - a[1] - (b[0] - b[1]));
const n = costs.length >> 1;
let ans = 0;
for (let i = 0; i < n; ++i) {
ans += costs[i][0] + costs[i + n][1];
}
return ans;
}func twoCitySchedCost(costs [][]int) (ans int) {
sort.Slice(costs, func(i, j int) bool {
return costs[i][0]-costs[i][1] < costs[j][0]-costs[j][1]
})
n := len(costs) >> 1
for i, a := range costs[:n] {
ans += a[0] + costs[i+n][1]
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | The time complexity of this algorithm is O(n log n) due to the sorting mechanism and the space complexity is O(1). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Assignment | O(2^n) | O(n) | Conceptual understanding or very small inputs |
| Dynamic Programming (Balanced Assignment) | O(n^2) | O(n^2) | When exploring state transitions or learning DP modeling |
| Greedy with Sorting by Cost Difference | O(n log n) | O(1) | Optimal solution for interviews and production |
Frequently asked questions
Is Two City Scheduling easy or hard?
Two City Scheduling is rated Medium difficulty. The implementation is straightforward once you recognize the greedy insight of sorting by cost difference, but identifying that idea quickly is what makes the problem challenging during interviews.
How to solve Two City Scheduling in O(n)?
A strict O(n) solution is not typical because sorting is required to rank cost differences. The standard optimal solution sorts people by (costA - costB) and runs in O(n log n). Without sorting, it is difficult to guarantee the optimal assignment while maintaining the constraint that exactly n people go to each city.
What is the best approach for Two City Scheduling?
The best approach is a greedy strategy combined with sorting. Compute the difference between the cost of flying each person to city A and city B, then sort by this difference. Send the first n people to city A and the rest to city B. This ensures the largest cost savings are applied first and runs in O(n log n) time.
What data structure is used in Two City Scheduling?
The problem primarily uses arrays along with a sorting step. Each element contains the cost of sending a person to city A and city B. The algorithm sorts the array based on the difference between those two costs and then performs a simple iteration.
What is the time complexity of Two City Scheduling?
The optimal greedy solution runs in O(n log n) time because the main operation is sorting the cost differences. After sorting, a single pass assigns the first n people to city A and the remaining n to city B. Space complexity is O(1) if the sort is done in place.
Two City Scheduling Python or Java solution approach?
Both Python and Java implementations follow the same greedy logic. Sort the list of cost pairs using the difference (costA - costB), then sum the first n costs for city A and the remaining n costs for city B. The algorithm runs in O(n log n) time and uses constant extra space.
Is Two City Scheduling asked at Google, Amazon, or Meta?
Two City Scheduling represents a common greedy interview pattern and has appeared in interview preparation sets used by companies like Amazon, Google, and Meta. Variations of the problem test your ability to optimize assignments using sorting and greedy decision making.