Maximum Length of Pair Chain

Description

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: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:

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

Solution(javascript)

/*
 * @lc app=leetcode id=646 lang=javascript
 *
 * [646] Maximum Length of Pair Chain
 */

// @lc code=start
/** Greedy 和 MIT 算法课上的 Interval Scheduling 一样
 * @param {number[][]} pairs
 * @return {number}
 */
const findLongestChain = function (pairs) {
  pairs.sort(([, b], [, d]) => b - d)

  let currentEnd = pairs[0][1]
  let count = 1
  for (const [start, end] of pairs) {
    if (start > currentEnd) {
      count += 1
      currentEnd = end
    }
  }
  return count
}