Send 2n people to two cities at least cost: book everyone to B, sort by A minus B, and switch the cheapest half to A.
▼The problem
LeetCode 1029 (Medium). 2n people must travel; costs[i] = [aCost, bCost] is what person i costs to fly to city A or to city B. Send exactly n people to each city at the minimum total cost.
Examples (LeetCode's): [[10,20],[30,200],[400,50],[30,20]] → 110 (the first two to A, the last two to B; the walkthrough runs it) and [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] → 1859.
The solution
def two_city_sched_cost(costs):
costs.sort(key=lambda c: c[0] - c[1])
n = len(costs) // 2
total = 0
for i, (a, b) in enumerate(costs):
total += a if i < n else b
return totalTranscript
Two City Scheduling. Two n people must travel. Each has two prices: one for city A and one for city B. Send exactly n to each city, at the smallest total cost.
Take four travelers: ten or twenty, thirty or two hundred, four hundred or fifty, thirty or twenty. Two go to each city; the best split costs one hundred ten.
The direct way tries every choice of n people for city A. Four travelers give six splits; twenty give one hundred eighty-four thousand, seven hundred fifty-six.
The key idea: first, book everyone to city B. That's two hundred ninety. Moving one traveler to A changes the total by their A price minus their B price, and a negative change is a saving. So sort by A minus B, and move the first n to city A.
In code, sort the costs by A minus B. The first half pays their A price, the rest pay B, and we add it up.
Here the differences are minus ten, minus one seventy, three fifty and ten. Sorted, minus one seventy and minus ten come first, so they go to A: two ninety minus one eighty is one hundred ten. With six travelers, A still needs three, so after minus five eleven it takes the smallest extras, forty-five and one oh eight: eighteen fifty-nine.
Sorting takes n log n time; the sum is one pass, with constant extra space beside the sort.
Book everyone to B, sort by A minus B, and send the first half to A. That's Two City Scheduling.