This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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].

b'

\n\n

\n#### Approach #1: Dynamic Programming [Accepted]

\n

\n#### Approach #2: Greedy [Accepted]

\n

\n

'
\n

**Intuition**

If a chain of length `k`

ends at some `pairs[i]`

, and `pairs[i][1] < pairs[j][0]`

, we can extend this chain to a chain of length `k+1`

.

**Algorithm**

Sort the pairs by first coordinate, and let `dp[i]`

be the length of the longest chain ending at `pairs[i]`

. When `i < j`

and `pairs[i][1] < pairs[j][0]`

, we can extend the chain, and so we have the candidate answer `dp[j] = max(dp[j], dp[i] + 1)`

.

**Complexity Analysis**

- \n
- \n
Time Complexity: where is the length of

\n`pairs`

. There are two for loops, and dominates the sorting step. \n - \n
Space Complexity: for sorting and to store

\n`dp`

. \n

\n

**Intuition**

We can greedily add to our chain. Choosing the next addition to be the one with the lowest second coordinate is at least better than a choice with a larger second coordinate.

\n**Algorithm**

Consider the pairs in increasing order of their *second* coordinate. We\'ll try to add them to our chain. If we can, by the above argument we know that it is correct to do so.

**Complexity Analysis**

- \n
- \n
Time Complexity: where is the length of

\n`S`

. The complexity comes from the sorting step, but the rest of the solution does linear work. \n - \n
Space Complexity: . The additional space complexity of storing

\n`cur`

and`ans`

, but sorting uses space. Depending on the implementation of the language used, sorting can sometimes use less space. \n

\n

Analysis written by: @awice.

\n