问题：
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].
解决：
① 贪心算法。对于排序：
以 (8,9) (10,11) (1,100)为例：
按照数组第一个元素排序： (1,100)，(8,9)， (10,11) 。不能通过比较 [i][end] 和 [i+1][begin] 来增加链。 而如果按照数组第二个元素排序： (8,9) ，(10,11)， (1,100)，那么则可以通过比较 [i][end] 和 [i+1][begin] 来增加链。class Solution {//35ms
public int findLongestChain(int[][] pairs) { Arrays.sort(pairs, new Comparator<int[]>() {//升序 public int compare(int[] o1, int[] o2) { return o1[1] - o2[1]; } }); int res = 0; int pre = Integer.MIN_VALUE; for (int[] pair : pairs){ if (pair[0] > pre){ res ++; pre = pair[1]; } } return res; } }② 求最长的链对，可以将每个pair按照第一个数字排序。dp[i]储存的是从i结束的链表长度最大值。首先初始化每个dp[i]为1。然后对于每个dp[i]，找在 i 前面的索引 0~j，如果存在可以链接在i 前面的数组，且加完后大于dp[i]之前的值，那么则在dp[j]的基础上+1.
class Solution { //89ms
public int findLongestChain(int[][] pairs) { //Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));jdk1.8使用λ表达式 Arrays.sort(pairs, new Comparator<int[]>() {//升序 public int compare(int[] o1, int[] o2) { return o1[0] - o2[0]; } }); int max = 0; int len = pairs.length; int[] dp = new int[len]; Arrays.fill(dp,1); int i = 0; int j = 0; for (i = 1;i < len;i ++){ for (j = 0;j < i;j ++){ if (pairs[j][1] < pairs[i][0] && dp[i] < dp[j] + 1){ dp[i] = dp[j] + 1; } } } for (i = 0;i < len;i ++){ if (max < dp[i]){ max = dp[i]; } } return max; } }