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 Npeople arrive in each city.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Example 1:

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.

Note:

  1. 1 <= costs.length <= 100
  2. It is guaranteed that costs.length is even.
  3. 1 <= costs[i][0], costs[i][1] <= 1000

公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。

返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。

示例：

输入：[[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 A 市，费用为 10。
第二个人去 A 市，费用为 30。
第三个人去 B 市，费用为 50。
第四个人去 B 市，费用为 20。

最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

提示：

  1. 1 <= costs.length <= 100
  2. costs.length 为偶数
  3. 1 <= costs[i][0], costs[i][1] <= 1000
Runtime: 16 ms Memory Usage: 19.3 MB 
 1 class Solution {
 2     func twoCitySchedCost(_ costs: [[Int]]) -> Int {
 3         var base:Int = 0
 4         var n:Int = costs.count
 5         var cs:[Int] = [Int](repeating:0,count:n)
 6         for (index,cost) in costs.enumerated()
 7         {
 8             base += cost[0]
 9             cs[index] = cost[1] - cost[0]  
10         }
11         cs.sort()
12         for i in 0..<n/2
13         {
14             base += cs[i]
15         }
16         return base
17     }
18 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄