# 【LeetCode】 1029. Two City Scheduling

## Description
> There are `2N` people a company is planning to interview. The cost of flying the `i`-th person to city `A` is `costs[i][0]`, and the cost of flying the `i`-th person to city `B` is `costs[i][1]`.

> Return the minimum cost to fly every person to a city such that exactly `N` people arrive in each city.

> Note:
> * `1 <= costs.length <= 100`
> * It is guaranteed that `costs.length` is even.
> * `1 <= costs[i][0], costs[i][1] <= 1000`

> 一家公司預計有`2N`個人要來面試。第`i`個人要飛到城市`A`的費用為`costs[i][0]`，而第`i`個人要飛到城市`b`的費用為`costs[i][1]`。

> 回傳每個城市都剛好有`N`個人時，飛行所需要的最小花費。

> 注意：
> * `1 <= costs.length <= 100`
> * 保證 `costs.length` 是偶數。
> * `1 <= costs[i][0], costs[i][1] <= 1000`

## Example:

Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation: 
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

## Solution

* 這題的重點在於要如何分配哪`N`個人要到城市`A`、哪`N`個人要到城市`B`。
* 我們將`costs`重新排列，依據`[0] - [1]`。
* 以範例來說，會得到`-10, -170, 350, 10`，然後重新排序。
* 這個排序過後的陣列，越前面的就代表選`A`越省；反之越後面選`B`越省。
* 那麼我們就從中間切一半，前半選`A`、後半選`B`，計算總合即可。

### Code

bool myCompare(vector<int> a, vector<int> b)
{
    return a[0] - a[1] < b[0] - b[1];
}

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int sum = 0;
        sort(costs.begin(), costs.end(), myCompare);
        for(int i = 0; i < costs.size() / 2; i++)
        {
            sum += costs[i][0] + costs[costs.size() - 1 - i][1];
        }
        return sum;
    }
};

###### tags: `LeetCode` `C++`