# 1029. Two City Scheduling
###### tags: `Leetcode` `Medium` `Bloomberg` `Greedy`
Link: https://leetcode.com/problems/two-city-scheduling/
## 思路
O(NlogN) O(1)
用去A和去B的cost的差排序
前面n个选择去B后面n个选择去A
## Code

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        n = len(costs)//2
        costs.sort(key = lambda cost:cost[0]-cost[1])
        return sum(cost[0] for cost in costs[:n]) + sum(cost[1] for cost in costs[n:])

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        int totalPpl = costs.length;
        Arrays.sort(costs, (a,b)->(a[1]-a[0])-(b[1]-b[0]));
        int res = 0;
        for(int i = 0;i < totalPpl/2;i++){
            res+=costs[i][1];
        }
        for(int i = totalPpl/2;i < totalPpl;i++){
            res+=costs[i][0];
        }
        return res;
    }
}