[Swift]LeetCode646. 最长数对链 | Maximum Length of Pair Chain

概述You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of p

You are given n pairs of numbers. In every pair,the first number is always smaller than the second number.

Now,we define a pair (c,d) can follow another pair (a,b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs,find the length longest chain which can be formed. You needn‘t use up all the given pairs. You can select pairs in any order.

Example 1:

input: [[1,2],[2,3],[3,4]]Output: 2Explanation: The longest chain is [1,2] -> [3,4] 

Note:

The number of given pairs will be in the range [1,1000].

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c,d) 才可以跟在 (a,b) 后面。我们用这种形式来构造一个数对链。

给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 :

输入: [[1,4]]输出: 2解释: 最长的数对链是 [1,4]

注意：

给出数对的个数在 [1,1000] 范围内。 Runtime: 236 ms Memory Usage: 19.1 MB

 1 class Solution { 2     func findLongestChain(_ pairs: [[Int]]) -> Int { 3         var pairs = pairs 4         var res:Int = 0 5         var end:Int = Int.min 6         pairs.sort(by:{(a:[Int],b:[Int]) -> Bool in  7                        return a[1] < b[1]                       8                       }) 9         for pair in pairs10         {11             if pair[0] > end12             {13                 res += 114                 end = pair[1]15             }16         }17         return res18     }19 }

284ms

 1 class Solution { 2     func findLongestChain(_ pairs: [[Int]]) -> Int { 3         let sortPairs = pairs.sorted { $0[1] < $1[1] } 4         var ans = 0,curEnd = Int.min 5         for pair in sortPairs { 6             if pair[0] > curEnd { 7                 ans += 1 8                 curEnd = pair[1] 9             }10         }11         return ans12     }13 }

296ms

 1 class Solution {    2     func findLongestChain(_ pairs: [[Int]]) -> Int { 3     guard pairs.count > 1 else{ 4         return pairs.count 5     } 6     let sorted = pairs.sorted(by: {$0[1] < $1[1]}) 7     var count : Int = 1 8     var currentPair = sorted[0] 9     for pair in sorted{10         if pair.first! > currentPair.last!{11             count += 112             currentPair = pair13         }14     }    15     return count    16     }17 }

1260ms

 1 sample 1260 ms submission 2 class Solution { 3     func findLongestChain(_ pairs: [[Int]]) -> Int { 4         let n = pairs.count 5         if n <= 1{ return n } 6          7         let sorted = pairs.sorted { $0[0] < $1[0] } 8         var f = [Int](repeating: 1,count: n) 9         var result = 110         11         for i in 1..<n {12             for j in 0..<i {13                 if sorted[j][1] < sorted[i][0] {14                     f[i] = max(f[i],f[j] + 1)15                     result = max(result,f[i])16                 }17             }18         }19         20         return result21     }22 }

1272ms

 1 class Solution { 2     func findLongestChain(_ pairs: [[Int]]) -> Int { 3         guard pairs.count > 1 else { return 1 } 4         let pairs = pairs.sorted(by: { 5             return $0[0] < $1[0] 6         }) 7          8         let n = pairs.count 9         var dp: [Int] = Array(repeating: 0,count: n)10         dp[0] = 111         12         for i in  1 ..< n {13             for j in 0 ..< i {14                 if pairs[i][0] > pairs[j][1] {15                     dp[i] = max(dp[i],dp[j])16                 }17             }18             dp[i] += 119         }20         21         return dp[n - 1]22     }23 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode646. 最长数对链 | Maximum Length of Pair Chain全部内容，希望文章能够帮你解决[Swift]LeetCode646. 最长数对链 | Maximum Length of Pair Chain所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。