A firm must send exactly half of its 2n auditors to site A and the other half to site B. costs[i] = [a, b] gives the travel cost of auditor i to site A and to site B respectively. Return the minimum total travel cost.
Examples
Input: costs = [[8, 2], [5, 9], [4, 4], [7, 1]]
Output: 12
Explanation: Send auditors 1 and 2 to A (5 + 4) and auditors 0 and 3 to B (2 + 1).
Input: costs = [[1, 100], [1, 100]]
Output: 101
Constraints
len(costs)is even,0 <= len(costs) <= 5 * 10**4,0 <= a, b <= 10**6.- Target complexity: O(n log n).
Goals
- Sort by the cost difference so each choice is judged by what it saves
- Argue that taking the n most site-A-favourable auditors is optimal