丹徒网站建设要多少钱,51网站一起做网店,张掖网站制作,视频拍摄团队LCR 074. 合并区间 - 力扣#xff08;LeetCode#xff09;
题目描述
以数组 intervals 表示若干个区间的集合#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间#xff0c;并返回一个不重叠的区间数组#xff0c;该数组需恰好覆盖输入中…LCR 074. 合并区间 - 力扣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 104intervals[i].length 20 starti endi 104 题解
判断区间重叠 如图所示如果后边区间的开始端点位置小于等于前边区间结束端点的位置就说明这两个区间是重叠的即intervals[j][0]intervals[i][1]
故本题的解题思路如下 对区间按照开始端点进行排序以方便判断重叠区间定义一个结果数组res将第一个区间放入到res中遍历区间数组intervals如果intervals[i][0]res.back()[1]说明当前遍历到的区间与res中的区间产生了重叠此时只需更新res的尾端点即可选取最大的尾端点否则说明遍历到的区间与res中的区间与res中的区间没有产生重叠故直接放入res结果集中即可 代码
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {if(intervals.size()0) return {};//排序sort(intervals.begin(),intervals.end(),[](const vectorint v1,const vectorint v2){return v1[0]v2[0]; });vectorvectorint res;res.emplace_back(intervals[0]);for(int i1;iintervals.size();i){//有重叠就合并if(intervals[i][0]res.back()[1])res.back()[1]max(res.back()[1],intervals[i][1]);//无重叠就直接加入elseres.emplace_back(intervals[i]);}return res;}
};
