Split Candidates Between Two Cities
Problem
A company is flying an even number of candidates to on-site interviews, and exactly half must go to office A and half to office B. costs[i] = [a, b] gives the fare for candidate i to each office. Return the lowest total fare that sends exactly half of the candidates to each office.
Examples
Input: costs = [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110
Why: the first two go to A for 10 + 30, the last two to B for 50 + 20Input: costs = [[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]]
Output: 1859Input: costs = [[5, 5], [7, 7]]
Output: 12
Why: edge case, both offices cost the same, so any even split is optimalHints
0 / 3
Sending everyone to their cheaper office fails when too many prefer the same one. Think about what it costs to move one candidate from A to B.
Moving candidate i from A to B changes the total by b minus a. Those who save the most by flying to A should be the ones who get A.
Sort the candidates by a minus b, from most negative to most positive. Send the first half to A and the second half to B, and add up the fares.
Solution
Picture everyone flying to B first; switching candidate i to A then changes the total by a minus b, and exactly half of the candidates must switch. The cheapest way to choose them is to take the half with the smallest values of a minus b, so the list is sorted by that difference and split down the middle. An exchange argument confirms it: swapping any A candidate for a B candidate with a smaller difference could only lower the total. Time is O(n log n) for the sort and space is O(n) for the sorted copy.
def split_cities(costs):
costs = sorted(costs, key=lambda c: c[0] - c[1]) # most eager for A first
half = len(costs) // 2
return sum(a for a, _ in costs[:half]) + sum(b for _, b in costs[half:])
print(split_cities([[10, 20], [30, 200], [400, 50], [30, 20]])) # -> 110
print(split_cities([[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]])) # -> 1859
print(split_cities([[5, 5], [7, 7]])) # -> 12Stuck on the idea rather than the code? Sorting Basics covers it.