646 Maximum Length of Pair Chain
Last updated
Was this helpful?
Last updated
Was this helpful?
You are givenn
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 ifb < 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:
Note:
The number of given pairs will be in the range [1, 1000].
(1) Sorting + DP
Sorting + DP:时间复杂度O(nlogn + n^2), n为pairs的个数, 空间复杂度O(n)