Leetcode 435 无重叠区间
2023-12-22 17:44:48
题意理解:
????????给定一个区间的集合 intervals
? ? ? ? 要求需要移除区间,使剩余区间互不重叠?
? ? ? ? 目标:最少需要移除几个区间。
解题思路:
? ? ? ? 采用贪心思路解题,什么是全局最优解,什么是局部最优解。
? ? ? ? 全局最优解,删除最少的区间,使剩下的区间不重叠。
? ? ? ? 局部最优:尽可能识别重叠的区域,并移除相应区间。
? ? ? ? 为了方便识别重叠区间,我们以区间的左边界为准升序排列,左区间一致,以右区间升序排列。
? ? ? ? 最终的序列:同起点的区间,小区间总在最前面。
? ? ? ? 当第i个区间的左边界<第i-1个区间的右边界时,出现重叠区域,需要删除的count++;
? ? ? ? 当删除该区间后,第i+1个元素的左边界和最早截止的区间的右边界比较,以保证更多的不重叠区间。
? ? ? ? 为了方便统一处理,当记录删除一个区间时:
????????????????将要删除第i的区间右边界设为Math.min(第i-1区间的右边界,第i个区间的右边界)
????????
????????
1.贪心解题
我们使用count记录发生重叠要删除的区域。
public int eraseOverlapIntervals(int[][] intervals) {
int count=0;
//对区间进行排序
Arrays.sort(intervals,(o1,o2)->(o1[0] - o2[0]));
//遍历区间,总是和最左边的区间比较
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]<intervals[i-1][1]){//有重叠
count++;
intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);
}
//无重叠,不操作
}
return count;
}
2.分析
时间复杂度:O(n logn) 排序所需时间O(nlogn)+遍历的时间O(n)
空间复杂度:O(logn) 排序所需的额外栈空间O(logn)
n为输入数组的大小
文章来源:https://blog.csdn.net/lt_BeiMo/article/details/135154358
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!