北海网站建设网,网线制作过程,长沙装修公司招聘网,建站素材网站模板今日主要总结一下可以使用贪心算法解决的一道题目#xff0c;56. 合并区间
题目#xff1a;56. 合并区间
Leetcode题目地址 题目描述#xff1a; 以数组 intervals 表示若干个区间的集合#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间…今日主要总结一下可以使用贪心算法解决的一道题目56. 合并区间
题目56. 合并区间
Leetcode题目地址 题目描述 以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。
示例 1 输入intervals [[1,3],[2,6],[8,10],[15,18]] 输出[[1,6],[8,10],[15,18]] 解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2 输入intervals [[1,4],[4,5]] 输出[[1,5]] 解释区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示
1 intervals.length 10^4 intervals[i].length 2 0 starti endi 10^4
本题重难点 这道题主要就分为三种情况
一个区间包含另一个区间两个区间有交集两个区间没有交集
写法一
C代码
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint res;sort(intervals.begin(), intervals.end());for(int i 0; i intervals.size(); i){int start intervals[i][0], end intervals[i][1];while(i intervals.size() - 1 end intervals[i 1][0]){end max(end, intervals[i 1][1]);start min(start, intervals[i 1][0]);i;}res.push_back({start, end});}return res;}
};写法二
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint res;sort(intervals.begin(), intervals.end());res.push_back(intervals[0]);for(int i 1; i intervals.size(); i){if(intervals[i][0] res.back()[1]){ // 出现重叠\// 合并区间// 此时由于已经按照左边界排好序intervals[i - 1][0] 一定intervals[i][0]// 所以只需要更新右边界res.back()[1] max(res.back()[1], intervals[i][1]);}else{res.push_back(intervals[i]);}}return res;}
};以上两种写法都可以看哪个容易理解会写一种写法就行 总结
这道题主要就分为三种情况
一个区间包含另一个区间两个区间有交集两个区间没有交集
本文给出了两种写法大家看哪个容易理解会写一种写法就行 但这道题目本质上还是区间重叠问题的加强版欢迎大家关注本人公众号编程复盘与思考随笔(关注后可以免费获得本人在csdn发布的资源源码)
