Consistently 99.9%+... dead simple

  • 0

    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);
        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.