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

The first thought of this problem is to sort the array and uses DP. However, it requires O(n2) complexity so definitely won't be accepted.

To optimize, we still sort the array. Instead of using regular sorting method, we put a[i] in front of a[j] if a[i][0] = a[j][0] && a[i][1] > a[j][1]. I will explain why we do this later.

Then we create a list and use binary search to find the position of each element in the list. If the position is larger than the size of the list, we append the element to the list, otherwise we set the value of the position as the element.

Now let's explain why we want to reverse the order if two elements contains the same a[i][0]. Consider we order it in the normal way. Then the position of the new element will get a position that is larger than the inserted one, which has the same a[i][0]. This will make us insert one more element, which is not correct.

Note:
1. why do we need to do "low <= high" instead of "low < high"?
Because if the first element is [2, 3] and the second is [5, 4], we want to add a new one instead of overriding the first one.
2. Why do we only check midA[1] < curr[1]?
Because we sort the array by o1[0] < o2[0], so curr[0] is guaranteed to be at least equal to midA[1].

public int maxEnvelopes(int[][] envelopes) {
              int len = envelopes.length;
        if (len <= 1) {
            return len;
        }
        Arrays.sort(envelopes, new Comparator() {

            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] < o2[0] || (o1[0] == o2[0] && o1[1] > o2[1]))
                    return -1;
                else if (o1[0] == o2[0] && o1[1] == o2[1])
                    return 0;
                else
                    return 1;
            }
        });

        List<int[]> rst = new ArrayList<>();
        for (int[] curr : envelopes) {
            int low = 0, high = rst.size() - 1;
            while (low <= high) {
                int mid = (low + high) / 2;
                int[] midA = rst.get(mid);
                if (midA[1] < curr[1]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            if (low < rst.size()) {
                rst.set(low, curr);
            } else {
                rst.add(curr);
            }


        }
        return rst.size();
        
    }