【力扣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: vector<vector<int>> merge(vector<vector<int>>& intervals) { vector<vector<int>> res; sort(intervals.begin(),intervals.end()); res.push_back(intervals[0]); for(int i=1;i<intervals.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; } };