[Swift]LeetCode1029.两地调度|TwoCityScheduling

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10744640.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.

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 <= 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]，飞往 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 <= costs.length <= 100
costs.length 为偶数
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 }

16ms

 1 class Solution {
 2     func twoCitySchedCost(_ costs: [[Int]]) -> Int {
 3         var costDiff = costs.sorted(by: { $0[1] - $0[0]  > $1[1] - $1[0] })
 4         var minCost = 0
 5         for i in 0..<costs.count {
 6             if i < costs.count / 2 {
 7                 minCost += costDiff[i][0]
 8             } else {
 9                 minCost += costDiff[i][1]
10             }
11         }
12         return minCost
13     }
14 }

20ms

 1 class Solution {
 2     func twoCitySchedCost(_ costs: [[Int]]) -> Int {           
 3         let costs = costs.sorted { (a, b) in
 4             return abs(a[0] - a[1]) > abs(b[0] - b[1])
 5         }
 6         let N = costs.count / 2
 7         var c1 = 0, c2 = 0, ans = 0
 8         for i in 0..<2*N {
 9             if ((costs[i][0] < costs[i][1] && c1 < N) || c2 == N) {
10                 ans += costs[i][0]
11                 c1 += 1
12             }
13             else {
14                 ans += costs[i][1]
15                 c2 += 1
16             }
17         }
18         return ans
19 
20     }
21 }

24ms

 1 class Solution {
 2     func twoCitySchedCost(_ costs: [[Int]]) -> Int {
 3         
 4         var count = 0
 5         var deltaAtoB = [Int]()
 6         var deltaBtoA = [Int]()
 7         var result = 0
 8         for cost in costs {
 9             if cost[0] <= cost[1] {
10                 count += 1
11                 result += cost[0]
12                 deltaBtoA.append(cost[1] - cost[0])
13             } else {
14                 count -= 1
15                 result += cost[1]
16                 deltaAtoB.append(cost[0] - cost[1])
17             }
18         }
19 
20         if count == 0 {
21             return result
22         } else if count > 0 {
23             deltaBtoA.sort()
24             for i in 0..<count/2 {
25                 result += deltaBtoA[i]
26             }
27         } else {
28             deltaAtoB.sort()
29             for i in 0..<abs(count)/2 {
30                 result += deltaAtoB[i]
31             }
32         }
33         return result
34     }
35 }

28ms

 1 class Solution {
 2     func twoCitySchedCost(_ costs: [[Int]]) -> Int {
 3         var costDiff = costs.sorted(by: { $0[1] - $0[0]  > $1[1] - $1[0] })
 4         var minCost = 0
 5         for i in 0..<costs.count {
 6             if i < costs.count / 2 {
 7                 minCost += costDiff[i][0]
 8             } else {
 9                 minCost += costDiff[i][1]
10             }
11         }
12         return minCost
13     }
14 }

32ms

 1 class Solution {
 2     func twoCitySchedCost(_ costs: [[Int]]) -> Int {
 3         let N = costs.count / 2
 4         var dp = [[Int]]()
 5         
 6         for i in 0...N {
 7             let row = Array(repeating: 0, count: N+1)
 8             dp.append(row)
 9         }
10         
11         for i in 1...N {
12             dp[i][0] = dp[i-1][0] + costs[i-1][0]
13         }
14         
15         for j in 1...N {
16             dp[0][j] = dp[0][j-1] + costs[j-1][1]
17         }
18         
19         for i in 1...N {
20             for j in 1...N {
21                 dp[i][j] = min(dp[i-1][j] + costs[i+j-1][0], dp[i][j-1] + costs[i+j-1][1])
22             }
23         }
24         
25         return dp[N][N]
26     }
27 }

44ms

 1 class Solution {
 2     func twoCitySchedCost(_ costs: [[Int]]) -> Int {
 3         var costsrt = costs.sorted(by: {return abs($0[0]-$0[1]) >= abs($1[0]-$1[1])})
 4         
 5         var N = costs.count / 2
 6         var A = 0
 7         var B = 0
 8         var ac = 0
 9         var bc = 0
10         
11         for p in costsrt {
12             if (p[0] > p[1] && bc < N) || ac == N {
13                 B += p[1]
14                 bc += 1
15                 print("B:", p[1])
16             } else {
17                 A += p[0]
18                 ac += 1
19                 print("A:", p[0])
20             }
21         }
22         
23         return A+B
24     }
25 }