leetcode@ [354] Russian Doll Envelopes (Dynamic Programming)

class pair {
    public int width;
    public int height;
    
    public pair(int w, int h) {
        super();
        this.width = w;
        this.height = h;
    }
}

class pairComparator implements Comparator {
    public int compare(Object o1, Object o2) {
        pair p1 = (pair) o1;
        pair p2 = (pair) o2;
        
        if(p1.width < p2.width) {
            
            return -1;
            
        } else if(p1.width == p2.width) {
            
            if(p1.height == p2.height) {
                return 0;
            } else if(p1.height < p2.height) {
                return -1;
            } else {
                return 1;
            }
            
        } else {
            
            return 1;
        }
    }
}

public class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        
        int n = envelopes.length;
        if(n == 0) {
            return 0;
        }
        
        pair pr[] = new pair[n];
        for(int i=0; i<n; ++i) {
            pair p = new pair(envelopes[i][0], envelopes[i][1]);
            pr[i] = p;
        }
        
        Arrays.sort(pr, new pairComparator());
        
        int[] dp = new int[n];
        int rs = -1;
        for(int i=0; i<n; ++i) {
            int mmax = 0;
            for(int pre=0; pre<i; ++pre) {
                if(pr[pre].width < pr[i].width && pr[pre].height < pr[i].height) {
                    mmax = Math.max(mmax, dp[pre]);
                }
            }
            dp[i] = mmax + 1;
            rs = Math.max(rs, dp[i]);
        }
        
        return rs;
    }
}