Java O(nlogn) solution using sort and greedy.


  • 0

    The greedy idea is if one pair's end is smaller than the other one, pick the smaller end one first.
    The start point is just used to check if the 2 pairs can form a chain.

    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (int[] a, int[]b) -> a[1] - b[1]);
        int res = 1;
        int last = pairs[0][1];
        for (int i = 1; i < pairs.length; i++) {
            if (pairs[i][0] > last) {
                res ++;
                last = pairs[i][1];
            }
        }
        return res;
    }

Log in to reply
 

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