Very easy Greedy Algrithm [sort: O(nlgn) + greedy: O(n)]


  • 0
    K

    The idea is to keep the end minimum when curStart < end.

    class Solution {
        public int findLongestChain(int[][] pairs) {
            if (pairs == null || pairs.length == 0 || pairs[0] == null || pairs[0].length == 0) {
                return 0;
            }
            Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
            int start = 0, end = 0;
            int count = 0;
            for (int[] pair : pairs) {
                int curS = pair[0];
                int curE = pair[1];
                if (start == 0 && end == 0) {
                    start = curS;
                    end = curE;
                } else {
                    if (curS <= end) {
                        end = Math.min(end, curE);
                    } else {
                        count++;
                        start = curS;
                        end = curE;
                    }
                }
            }
            return count + 1;
        }
    }
    

Log in to reply
 

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