Russian Dolls | DP | Similar to box stacking.
Pingu
627

I tried solving Russian Doll Envelopes, I could solve in O(N2) time.

In solution there is given O(N Log N) solution, using binary search. I am aware of this approach for LIS problem but I am not getting the rationale behind the sorting logic that's being used there.

Can anyone help me to understand this.

        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] arr1, int[] arr2) {
                if (arr1[0] == arr2[0]) {
                    return arr2[1] - arr1[1];
                } else {
                    return arr1[0] - arr2[0];
                }
           }
        });
Comments (1)