Friday, August 25, 2017

646. Maximum Length of Pair Chain

用的是greedy的思想
sort all intervals by their end points
Increase the count by 1
Greedily looking for the 1st next point whose start point is larger than the current point
Set current end value as the new current point's end

46.73 %
class Solution {
    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) return 0;
        // sort by the end point
        Arrays.sort(pairs, (a, b) -> (a[1] - b[1]));
        int currEnd;
        int count = 0;
        int i = 0;
        while (i < pairs.length) {
            count++;
            currEnd = pairs[i][1];
            i++;
            while (i < pairs.length && pairs[i][0] <= currEnd) {
                i++;
            }
        }
        return count;
    }
}

No comments:

Post a Comment