public class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0]) {
                    return a[0] - b[0];
                } else {
                    return b[1] - a[1];
                }
            }
        });
        final List<int[]> tails = new ArrayList<>();
        for (int i=0; i<envelopes.length; i++) {
            if (tails.isEmpty() || envelopes[i][1] > tails.get(tails.size()-1)[1]) {
                tails.add(envelopes[i]);
            } else {
                int p = 0, r = tails.size()-1;
                while (p < r) {
                    final int q = p+(r-p)/2;
                    if (envelopes[i][1] <= tails.get(q)[1]) {
                        r = q;
                    } else {
                        p = q+1;
                    }
                }
                tails.set(p, envelopes[i]);
            }
        }
        return tails.size();
    }
}
