[JAVA] track end with iteration / T : O(N), S : O(1)


  • 0
    J

    If current end is smaller, We can chain it. (update end max)
    If current end is larger, We can't chain it. But we can replace last chain with it if end is smaller.

    class Solution {
        public int findLongestChain(int[][] pairs) {
            if(pairs.length == 0)
                return 0;
            
            Arrays.sort(pairs, (p1, p2)->{
                if(p1[0] == p2[0]){
                    return p1[1] - p2[1];
                }
                return p1[0] - p2[0]; 
            });
            
            int end = pairs[0][1];
            int count = 1;
            
            for(int i = 1; i < pairs.length; i++){
                if(end < pairs[i][0]){
                    end = Math.max(pairs[i][1], end);
                    count++;
                }
                else{
                    end = Math.min(pairs[i][1], end);
                }
            }
            
            return count;
        }
    }
    

Log in to reply
 

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