Description

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

1. 对整个二维数组进行sort

2. 优化查找， 用Binary search。但不是对整个二维数组进行二分，因为比如[14, 17]处的最大长度为4, [18, 13]处的最大长度为3，那么[18, 19]处的结果应该是去[14. 17]为前一个，即4+1=5
   因为按envelope[0]肯定是递增的，那么把拥有相同长度结果的envelope[1]记录下来， 即可得到一个envelope[1]也递增的序列，在此基础上进行二分
   sort后的数组已经对width进行了排序，所以Binary Search只要对height进行处理就行了。其实是要找到比当前height小的height使得得到的结果最大。不需要开辟额外的内存空间，直接用envelop数组，envelope[i][1]用于存放结果是i+1的，最小的height。

3. Binary Search遇到一个情况，如果一开始的sort是按照width，height都是递增的排序，那width相同的很难处理。比如[2, 13], [4, 17], [5, 7], [8, 9], [8, 19]. [4, 17]和[8, 9]都是2，但是如果把envelope[1][1]更新成[9]，在这里我们不能够是去[4, 17]的信息。所以只要在sort的时候，对相同width进行height递减排序即可。这样能够保证[8, 19]是3,而[8, 9]也会更新到envelop[2]上面。

public class Solution {
    /*
     * @param envelopes: a number of envelopes with widths and heights
     * @return: the maximum number of envelopes
     */
    public int maxEnvelopes(int[][] envelopes) {
        // write your code here
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }

        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0]) {
                    return a[0] - b[0];
                }

                return b[1] - a[1];
            }
        });

        int index = 0;
        int n = envelopes.length;
        for (int i = 1; i < n; i++) {
            int ret = binarySearch(envelopes, i, index);
            envelopes[ret][1] = envelopes[i][1];
            index = Math.max(ret, index);
        }

        return index + 1;
    }

    private int binarySearch(int[][] envelopes, int i, int index) {
        int start = 0;
        int end = index;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (envelopes[mid][1] < envelopes[i][1]) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (envelopes[end][1] < envelopes[i][1]) {
            return end + 1;
        } else if (envelopes[start][1] < envelopes[i][1]) {
            return start + 1;
        }

        return start;
    }
}