用的是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