Share my java greedy solution - 36ms


  • 0
    S

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

Log in to reply
 

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