题目

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:
The number of given pairs will be in the range [1, 1000].

答案

方法1，sort then count

class Solution {
    public int findLongestChain(int[][] pairs) {
        int count = 1;
        // Sort the pairs based on its starting time
        Arrays.sort(pairs, (a,b) -> a[1] - b[1]);
        int last = pairs[0][1];
        for(int i = 1; i < pairs.length; i++) {
            if(pairs[i][0] > last) {
                last = pairs[i][1];
                count++;
            }
        }
        return count;
    }
}

方法2，sort then LIS的变形

class Solution {
    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        // Sort the pairs based on its starting time
        Arrays.sort(pairs, (a,b) -> a[1] - b[1]);
        int[] sentinel = {Integer.MIN_VALUE, Integer.MIN_VALUE};
        int[][] lc = new int[n + 2][n + 2];
        for(int i = n; i >= 0; i--) {
            for(int j = n + 1; j > i; j--) {
                if(j > n) {
                    lc[i][j] = 0;
                    continue;
                }
                int[] pair_i = (i < 1) ? sentinel:pairs[i - 1];
                int[] pair_j = pairs[j - 1];

                if(pair_j[0] > pair_i[1]) {
                    lc[i][j] = Math.max(lc[j][j + 1] + 1, lc[i][j + 1]);
                }
                else {
                    lc[i][j] = lc[i][j + 1];
                }

            }
        }
        return lc[0][1];
    }
}