Leet Code 354. Russian Doll Envelopes

https://leetcode.com/problems/russian-doll-envelopes/

package pep.Day85;

import java.util.Arrays;

public class LeetCode_354_Russian_Doll_Envelopes {
    public static void main(String[] args) {
        int[][] envelopes = {{5, 4}, {6, 4}, {6, 7}, {2, 3}};
        System.out.println(maxEnvelopes(envelopes));
    }

    public static class Pair implements Comparable<Pair> {
        int width;
        int height;

        Pair(int width, int height) {
            this.width = width;
            this.height = height;
        }

        @Override
        public int compareTo(Pair o) {
            if (this.width != o.width) {
                // increasing width
                return this.width - o.width;
            } else {
                // decreasing on the basis of height
                return o.height - this.height;
            }
        }
    }

    public static int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        Pair[] arr = new Pair[n];

        for (int i = 0; i < n; i++) {
            arr[i] = new Pair(envelopes[i][0], envelopes[i][1]);
        }

        Arrays.sort(arr);

        // LIS on height
        int maxLength = 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int endIndex = 1; endIndex < n; endIndex++) {
            for (int startIndex = 0; startIndex < endIndex; startIndex++) {
                if (arr[startIndex].height < arr[endIndex].height) {
                    dp[endIndex] = Math.max(dp[endIndex], dp[startIndex] + 1);
                }
            }

            if (dp[endIndex] > maxLength)
                maxLength = dp[endIndex];
        }

        return maxLength;
    }
}