【力扣hot100】 56. 合并区间

一、题目以数组 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] 可被视为重叠区间。 示例 3 输入intervals [[4,7],[1,4]] 输出[[1,7]] 解释区间 [1,4] 和 [4,7] 可被视为重叠区间。 提示 1 intervals.length 104 intervals[i].length 2 0 starti endi 104二、思路没啥思路第一时间没想到办法就直接暴力了。将intervals数组排序后把intervals[0]放入res数组。然后for循环遍历如果 [i] 的左区间小于或等于 [i-1] 的右区间的同时右区间大于 [i-1] 的右区间就直接合并将 [i-1] 的右区间直接置为 [i] 的右区间。如果 [i] 的左区间大于 [i-1] 的右区间则直接将 [i] 区间加入res数组即可不合并。三、题解class Solution { public: vectorvectorint merge(vectorvectorint intervals) { vectorvectorint res; sort(intervals.begin(),intervals.end()); res.push_back(intervals[0]); for(int i1;iintervals.size();i){ if(intervals[i][0]res[res.size()-1][1] intervals[i][1]res[res.size()-1][1]){ res[res.size()-1][1]intervals[i][1]; } else if(intervals[i][0]res[res.size()-1][1]){ res.push_back(intervals[i]); } } return res; } };