354 Russian Doll Envelopes (Hard)

俄罗斯套娃信封问题

You have a number of envelopes with widths and heights given as a pair of integers(w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:

Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Solution:

俄罗斯套娃信封问题的本质是一个二维版的 LIS（最长递增子列）的问题。

1. Sort the array. Ascend on width and descend on height if width are same.
2. Find the longest increasing subsequence based on height.
3. Since the width is increasing, we only need to consider height.
4. [3, 4] cannot contains [3, 3], so we need to put [3, 4] before [3, 3] when sorting otherwise it will be counted as an increasing number if the order is [3, 3], [3, 4]

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes == null || envelopes.length == 0 
           || envelopes[0] == null || envelopes[0].length != 2)
            return 0;

        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] arr1, int[] arr2){
                if(arr1[0] == arr2[0])
                    return arr2[1] - arr1[1];
                else
                    return arr1[0] - arr2[0];
           } 
        });

        int dp[] = new int[envelopes.length];
        int len = 0;

        for(int[] envelope : envelopes){
            int index = Arrays.binarySearch(dp, 0, len, envelope[1]);

            if(index < 0)
                index = -(index + 1);
            dp[index] = envelope[1];

            if(index == len)
                len++;
        } // for

        return len;
    }
}