Similar Idea, Shorter Version


  • 0

    Same idea as in https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation
    Lambda expression makes it concise.

    public class Solution {
        public int maxEnvelopes(int[][] envelopes) {
            int n = envelopes.length; 
            if (n == 0) return 0; 
            
            int[] tails = new int[n]; 
            int index = 0, len = 0; 
            
            Arrays.sort(envelopes, (env1, env2) -> {
                return env1[0] != env2[0] ? env1[0] - env2[0] : env2[1] - env1[1]; 
            }); 
            
            for (int[] env : envelopes) {
                index = Arrays.binarySearch(tails, 0, len, env[1]); 
                if (index < 0) index = ~index; 
                tails[index] = env[1]; 
                if (index == len) len++; 
            }
            
            return len; 
        }
    }

Log in to reply
 

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