O(nlogn) solution


  • 0
    S
    public int findLongestChain(int[][] pairs) {
        if(pairs.length == 0)
            return 0;
        Arrays.sort(pairs, new Comparator<int[]>(){
            @Override
            public int compare(int[] p1, int[] p2) {
                return p1[1] - p2[1];
            }
        });
        
        int max = pairs[0][1], count = 1;
        for(int i=1; i<pairs.length; ++i) {
            if(pairs[i][0] > max) {
                ++count;
                max = pairs[i][1];
            } 
        }
        return count;
    }

Log in to reply
 

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