佛山企业设计网站建设,三里河网站建设公司,郑州网站建设中国建设建设银行,发优惠券网站怎么做目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 描述#xff1a;
以数组 in…目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接力扣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[i].left的大小排序然后选出第一个为headerheader和后面的一一比较分为三种情况
* 1.header.rightinterval.left;此时说明两个区间不相交则把header加入out中并且更新interval为header
* 2.header.rightinterval.right;此时说明header完全覆盖interval则可以直接跳过
* 3.header.rightinterval.right;此时说明两个区间有相交则相互不能完全覆盖则更新header的right等于区间合并。
代码
class Solution56
{
public:vectorvectorint merge(vectorvectorint intervals){sort(intervals.begin(), intervals.end(), [](vectorint v1, vectorint v2){ return v1[0] - v2[0] 0; });vectorvectorint out;vectorint header;for (vectorint interval : intervals){if (header.size() 0){header interval;continue;}if ((header)[1] interval[0]){out.push_back(header);header interval;continue;}if ((header)[1] interval[1]){continue;}header[1] interval[1];}out.push_back(header);return out;}
};
