|
方法：贪心
class Solution {
public int videoStitching(int[][] clips, int time) {
//按左端点升序排列(左端点相同时，按右端点降序排列)
Arrays.sort(clips, (o1, o2) -> {
if (o1[0] == o2[0]) return o2[1] - o1[1];
return o1[0] - o2[0];
});
if (clips[0][0] != 0) return -1;
//由排序规则，保证第一个片段一定被选中
int ans = 1;
int end = clips[0][1];
for (int i = 1; i < clips.length; ) {
if (end >= time) return ans;
if (clips[i][0] > end) return -1;
int j = i, maxRight = 0;
while (j < clips.length && clips[j][0] <= end) {
maxRight = Math.max(maxRight, clips[j][1]);
j++;
}
if (maxRight >= time) return ans + 1;
if (maxRight <= end) return -1;
ans++;
end = maxRight;
i = j;
}
return end < time ? -1 : ans;
}
}
?
|
