Two City Scheduling
Medium · greedy
A company is flying its staff to two offices, one in city A and one in city B. There is an even number of people, and exactly half of them must be sent to each city.
You are given costs, where costs[i] = [a, b] means that person i costs a to send to city A and b to send to city B. Each person is sent to exactly one city.
Return the smallest possible total cost of sending everyone.
Examples
Example 1
Input: costs = [[5, 9], [8, 3], [7, 7], [2, 6]]
Output: 17
Send persons 0 and 3 to city A (5 + 2) and persons 1 and 2 to city B (3 + 7), for a total of 17.
Example 2
Input: costs = [[4, 4], [4, 4]]
Output: 8
Example 3
Input: costs = [[1, 100], [100, 1]]
Output: 2
Person 0 goes to city A and person 1 to city B.
Constraints
- 2 <= len(costs) <= 2000
- len(costs) is even.
- 1 <= costs[i][0], costs[i][1] <= 1000