559. Two-City Split
A company is sending an even number m of employees to two branch offices, city A and city B. For employee i, costs[i][0] is the travel and housing cost if they go to city A, and costs[i][1] is the cost if they go to city B. Every employee goes to exactly one city, and exactly m / 2 employees must be sent to each city.
Return the minimum possible total cost of the whole plan. The order of employees does not matter, and several employees may have identical cost pairs.
Aim for O(m log m) time. A table that decides, for each employee, how many have gone to city A so far needs about m^2 / 2 steps and is too slow when m reaches one hundred thousand. The result always fits in a 32-bit signed integer.
Example 1
- Input:
- costs = [[8,3],[4,10],[7,7],[1,9]]
- Output:
- 15
- Explanation:
Send employees 3 and 1 to city A (1 + 4) and employees 0 and 2 to city B (3 + 7), for a total of 15.
Example 2
- Input:
- costs = [[6,6],[6,6]]
- Output:
- 12
- Explanation:
All costs are equal, so any split costs 12.
Example 3
- Input:
- costs = [[1,30],[2,40],[3,50],[4,60]]
- Output:
- 77
- Explanation:
Employees 0 and 1 go to city B (30 + 40) and employees 2 and 3 go to city A (3 + 4), for a total of 77.
Constraints
2 ≤ costs.length ≤ 100000, andcosts.lengthis evencosts[i].length == 21 ≤ costs[i][0], costs[i][1] ≤ 10000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(m log m)
- Space
- O(m)