Minimize Travel Cost while Sending Half the People to Each City
Company: Infosys
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
For each of2*n people, `costs[i]` gives the travel costs to cities A and B. Send every person to exactly one city with exactly n people in each. Return the minimum total cost.
```cpp
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs);
};
```
### Examples
**Example 1:**
```text
Input: costs = [[20,60],[50,10],[30,40],[80,20]]
Output: 80
Explanation: Send the first and third people to A for20+30, and the other two to B for10+20. This also achieves each person's individual cheaper cost.
```
**Example 2:**
```text
Input: costs = [[5,8],[6,100]]
Output: 14
Explanation: Sending the second person to A and the first to B costs6+8=14; the opposite assignment costs105.
```
### Constraints
- `2*n == costs.length`.
- `2 <= costs.length <= 100`, and length is even.
- `1 <= aCost_i,bCost_i <= 1000`.
### Contract considerations
The costs are fixed per person and city; there are no route interactions or additional scheduling constraints.
```hint Read the boundary condition
Compare the extra cost of choosing A instead of B for each person.
```
### Boundary reminders
The costs are fixed per person and city; there are no route interactions or additional scheduling constraints.
Overview: Minimize Travel Cost while Sending Half the People to Each City. For each of2*n people, costs[i] gives the travel costs to cities A and B.