# Share my java greedy solution - 36ms

• This problem is similar to the optimal interval scheduling problem. The key idea is to sort pair based on the end (second number) instead of start (first number). Then we keep picking the next pair with smallest end, check if its start > currEnd.

Time complexity: O(nlogn) because of the sorting
Space complexity: O(1)

``````public class Solution {
//sort pairs according to their second number
//greedy approach: always pick valid one with smallest second number
//similar to the optimal interval scheduling problem
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, new Comparator<int[]>(){
public int compare(int[] a, int[] b){
//a[1]-b[1] might overflow, e.g. a[1] is Integer.MIN_VALUE
if(a[1] != b[1]){
return a[1] < b[1] ? -1 : 1;
}else if(a[0] != b[0]){
return a[0] < b[0] ? -1 : 1;
}else{
return 0;
}
}
});

int count = 0;
int currEnd = Integer.MIN_VALUE;
for(int[] pair : pairs){
if(pair[0] > currEnd){
count++;
currEnd = pair[1];
}
}

return count;
}
}
``````

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