354. Russian Doll Envelopes

Problem:

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

Analysis:

Two dimensional Longest increasing sub sequence. Convert this problem to 1D LIS. Sort the envelopes by width. So height becomes the 1D LIS. But if we have [3, 3], [3, 4], the former doll can not fit into the latter one. If there is a tie on width, sort height in desc order. 

Time:  O(nlogn).

Solution:

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0 || envelopes[0].length == 0)
            return 0;
        
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] == b[0]) 
                return b[1] - a[1];
            else
                return a[0] - b[0]; 
        });

        int[] tails = new int[envelopes.length];
        int len = 1;
        tails[0] = envelopes[0][1];
        for (int i = 1; i < envelopes.length; i++) { 
            if (envelopes[i][1] > tails[len - 1]) {
                tails[len++] = envelopes[i][1];  
            } else {
                int index = search(tails, envelopes[i][1], len - 1);
                tails[index] = envelopes[i][1];
            }
        }
        return len;
    }

    private int search(int[] tails, int target, int end) {
        int start = 0;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (tails[mid] <= target)
                start = mid;
            else 
                end = mid;
        } 
        return tails[start]  >= target ? start : end;
    } 
}