Russian Doll Envelopes

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

Tips:

给定一些信封的宽和长，当且仅当信封x的宽和长均小于另一个信封y时，x可以装入y，求最多可以嵌套的装几个？

求LIS可以直接简单的dp，设dp[i]为以i为结尾的LIS长度，则dp[i] = max(0,dp[j] | j<i && A[j] < A[i]) + 1

复杂度为O(n^2)，但可以优化到O(nlogn)，排序然后二分。

做二分法的时候要注意Arrays.binarySearch方法：

Arrays.binarySearch() returns ( - insertion_index - 1) in cases where the element was not found in the array. 
Initially the dp array is all zeroes. 
For all zeroes array the insertion index for any element greater than zero is equal to the length of the array (dp.length in this case).
This means that the number needs to be added to the end of the array to keep the array sorted.

Sort the array. Ascend on width and descend on height if width are same.

Find the longest increasing subsequence based on height.

Since the width is increasing, we only need to consider height.

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

Code:

O(n^2) 简单dp

public 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[] a, int[] b) {
                if (a[0] == b[0]) return b[1] - a[1];
                else return a[0] - b[0];
            }
        });
        int dp[] = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; i++) dp[i] = 1;
        int max = 1;
        for (int i = 0; i < envelopes.length; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[i][1] > envelopes[j][1]) dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

O(nlogn) 二分

public 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++;
        }
        return len;
    }
}