Maximum Length of Pair Chain

ou are givennpairs 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:

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

Tips:

1. 实际使用greedy，先排好序，然后找pairs[i + 1][0] <= end，此处end为chain头的尾。
2. Time complexity: O(nlogn)

Code:

public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });
        int res = 0;
        for (int i = 0; i < pairs.length; i++) {
            res++;
            int end = pairs[i][1];
            while (i + 1 < pairs.length && pairs[i + 1][0] <= end) {
                i++;
            }
        }
        return res;
    }
}