• 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;

}
``````

}

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