Consistently 99.9%+... dead simple


  • 0
    M

    All I do is repeatedly find the next valid pair (start > current end) that has the nearest possible end.

    Took some thinking but I realized this was way faster than all of the fancy DP solutions.. try it out

    Reason it works and is so simple is because I realized a greedy approach would suffice

    class Solution {

    public int findLongestChain(int[][] pairs) {
    
        // All starts larger than any number
        
        // Get number of all possible nodes beyond any given point O(n)
        
        // Compare all nodes
    
        // Pick valid nodes with nearest possible ends
        
        if(pairs.length < 2) return pairs.length;
        
        // Always get nearest ending
        
        int count = 0;
        
        int end = getNearest(pairs, Integer.MIN_VALUE);
        
        while(end != Integer.MIN_VALUE){
        
            end = getNearest(pairs, end);
            
            count++;
    
        }
        
        return count;
        
    }
    
    int getNearest(int[][] pairs, int end){
        
        int nearest = Integer.MAX_VALUE;
        
        for(int i=0;i<pairs.length;i++){
            
            if(pairs[i][0] > end){
                
                if(pairs[i][1] < nearest){
                    
                    nearest = pairs[i][1];
                    
                }
                
            }
            
        }
                
        return nearest == Integer.MAX_VALUE ? Integer.MIN_VALUE : nearest;
        
    }
    

    }


Log in to reply
 

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