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.