Straightforward Java solution


  • 0
    W
    public class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            if (envelopes == null || envelopes.length == 0) return 0;
            
            // sort the envelopes by their area
            Arrays.sort(envelopes, new Comparator<int[]>() {
                public int compare(int[] e1, int[] e2) {
                    return new Integer(e1[0] * e1[1]).compareTo(new Integer(e2[0] * e2[1]));
                }
            });
            
            int[] dp = new int[envelopes.length];
            dp[0] = 1;
            int maxSoFar = 1;
    
            for (int i = 1; i < envelopes.length; i++) {
                int j = i - 1;
                int maxFit = 0;
                
                // find the maximum number of envelopes to fit from the previous solutions
                while (j >= 0) {
                    if (canFit(envelopes[i], envelopes[j]) && dp[j] > maxFit) {
                        maxFit = dp[j];
                    }
                    j--;
                }
                dp[i] = maxFit + 1;
    
                maxSoFar = Math.max(maxSoFar, dp[i]);
            }
            
            return maxSoFar;
        }
        
        private boolean canFit(int[] outside, int[] inside) {
            return outside[0] > inside[0] && outside[1] > inside[1];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.