Two City Scheduling — Solution in Python, Java & C++
Two City Scheduling solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Two City Scheduling is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google, Adobe and Bloomberg interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google, Adobe, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A company is interviewing 2n people. Flying person i to city A costs costs[i][0], and flying them to city B costs costs[i][1].
Return the minimum total cost of flying exactly n people to each city.
Example 1
Input: costs = [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: Send the first two to A and the last two to B.
Example 2
Input: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
Output: 1859
Example 3
Input: costs = [[10,20],[20,10]]
Output: 20
Constraints
2 <= costs.length <= 40costs.length is even.1 <= costs[i][0], costs[i][1] <= 1000
Hints for Two City Scheduling
Hint 1
Imagine flying everyone to B first, then upgrading exactly
nof them to A.Hint 2
The cost of upgrading person
iiscosts[i][0] - costs[i][1], so upgrade thencheapest.Hint 3
Sorting by that difference and splitting the list in half does exactly that.
How to solve Two City Scheduling
Send everyone to B, then upgrade the n people whose A-minus-B difference is smallest (most negative). Sorting by that difference and splitting in half does it.
Approach
- Sort by
costA - costB. - Sum
costAfor the first half andcostBfor the second half.
Why it works
Exactly n must go to A, so the choice is which n. Relative to an all-B baseline, sending person i to A changes the total by costA - costB; choosing the n smallest deltas minimises the total.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Picking each person's cheaper city independently ignores the exactly-
nconstraint.
Reference solution
Python
def twoCitySchedCost(costs) -> int:
ordered = sorted(costs, key=lambda c: c[0] - c[1])
half = len(ordered) // 2
return sum(c[0] for c in ordered[:half]) + sum(c[1] for c in ordered[half:])Java
public static int twoCitySchedCost(int[][] costs) {
int[][] s = costs.clone();
Arrays.sort(s, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
int half = s.length / 2;
int total = 0;
for (int i = 0; i < s.length; i++) total += i < half ? s[i][0] : s[i][1];
return total;
}C++
int twoCitySchedCost(vector<vector<int>>& costs) {
vector<vector<int>> s = costs;
sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) {
return (a[0] - a[1]) < (b[0] - b[1]);
});
int half = (int) s.size() / 2;
int total = 0;
for (int i = 0; i < (int) s.size(); i++) total += i < half ? s[i][0] : s[i][1];
return total;
}JavaScript
var twoCitySchedCost = function(costs) {
const sorted = costs.slice().sort(function(a, b) { return (a[0] - a[1]) - (b[0] - b[1]); });
const half = sorted.length / 2;
let total = 0;
for (let i = 0; i < sorted.length; i++) {
total += i < half ? sorted[i][0] : sorted[i][1];
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms