class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>()
        {
            public int compare(int[] a, int[] b){
                return a[0] == b[0] ?
                    b[1] - a[1] : a[0] - b[0];
            }
        });
        int n = envelopes.length;
        int[] h = new int[n];
        for(int i = 0; i < n; i ++ ) {
            h[i] = envelopes[i][1];
        }
        return LIS(h);
    }

    public int LIS(int[] nums) {
        int len = 0, n = nums.length;
        int[] q = new int[n + 1];
        for(int i = 0; i < n; i ++ ) {
            int l = 0, r = len;
            int x = nums[i];
            while(l < r) {
                int mid = l + r + 1 >> 1;
                if(q[mid] < x) l = mid;
                else r = mid - 1;
            }
            q[l + 1] = x;
            len = Math.max(len, l + 1);
        }

        return len;
    }
}