[LeetCode 354] Russian Doll Enve

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)

Note:

• Rotation is not allowed.

Example:

Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3 
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

SOLUTION

1. 首先对envelopes按照width升序，height降序排序
2. 然后再对排序好的height用Longest Increasing Subsequence的方法来找套娃答案。

Note:

1. height必须降序，否则如果按照升序，那么按照例子升序排序为[[2,3],[5,4],[6,4],[6,7]]，[6, 7]就会被包含进去，但其实是不能包含的。
2. 需要处理重复出现的height, 否则重复出现的元素 例如[[2,6],[5,7],[5,6],[6,7],[6,4]] 如果不处理重复的6，那么最后得到的result就会是[4,6,7]，长度为3，结果错误

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0 || envelopes[0].length == 0)
            return 0;
        
        //1. sort envelops first based on width (ascending), then if width is idential based on height (descending)
        // customize comparator interface
        Arrays.sort (envelopes, new Comparator <int []> () {
            
            public int compare (int[] envelop1, int [] envelop2) {
                if (envelop1 [0] != envelop2 [0]) {
                    return envelop1 [0] - envelop2 [0];
                } else {
                    return envelop2 [1] - envelop1 [1];
                }
            }
        });
        
        for (int i = 0; i < envelopes.length; i ++) {
                System.out.println ("[" + envelopes[i][0] + "," + envelopes[i][1] + "]");
        }
        
        //2. using Longest Increasing Subsequence solution to handle the height
        List<Integer> result = new ArrayList<> ();
        result.add (envelopes [0][1]);
        
        for (int[] size : envelopes) {
            int height = size[1];
            int resultLastIndex = result.size () - 1;
            
            if (height > result.get (resultLastIndex)) {
                result.add (height);
            } else if (height < result.get (0)) {
                result.set (0, height);
            } else {
                if (!result.contains (height)) {
                    int start = 0;
                    int end = resultLastIndex;
                    
                    while (start < end) {
                        int middle = start + (end - start) / 2;
                        if (height > result.get (middle)) {
                            start = middle + 1;
                        } else {
                            end = middle;
                        }
                    }
                    
                    result.set (start, height);
                }
            }
        }
        return result.size ();
        
    }
}