Send people to two cities
Fly half the people to each of two cities at the lowest total cost, by sorting people on how much cheaper city A is than city B. About 15 minutes.
Compare by the difference
A company flies 2n people to interview: exactly n go to city A and n go to city B. Each person has a cost for each city. You want the lowest total.
Looking at one cost alone misleads. What matters is how much you gain by sending a person to A rather than B. Start by pretending everyone goes to B, then ask who saves the most by switching to A.
Sort and split
Sort people by cost of A minus cost of B, smallest first. The people at the front gain the most from going to A, or lose the least.
Send the first n of them to A and the remaining n to B. Add up the matching costs. Swapping any pair across the split could only make the sum larger, which is why the greedy order is safe.
people.sort(key=lambda p: p[0] - p[1])
half = len(people) // 2
total = 0
for i, (a, b) in enumerate(people):
total += a if i < half else b- total
- 30
P2 saves 170 by going to A. Send to A.
Costs [A, B]: [10, 20], [30, 200], [400, 50], [30, 20]. Who is sent to A first?
- AThe person with costs [30, 200]
- BThe person with costs [10, 20]
- CThe person with costs [400, 50]
Show the answer
The person with costs [30, 200]. A costs 170 less than B for them, the biggest saving.
Send to two cities
You must send 2n people to two cities, exactly n to each. You are given costs, where costs[i] = [a, b] is the cost of sending person i to city A and city B. Return the lowest total cost.
costs = [[10, 20], [30, 200], [400, 50], [30, 20]] → 110
0 ≤ costs.length ≤ 100,000 and even · 1 ≤ a, b ≤ 1,000