算法小练习：56. 合并区间

小记：昨天室友面试字节跳动，出了这道题，然后当时我觉得这道题应该见过，原题是日本人写的一本算法竞赛书上的经典问题，这里我主要参考是《算法笔记》———胡凡、曾磊主编的那本，书上讲的是区间贪心问题，书上虽然求的是不可合并的区间个数，但是方法很巧妙，先对那些个区间的左端点进行从大到小的排序，如果一个区间的右端点小于选中区间的左端点，那么代表不可合并，ans++。

LeetCode 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] 可被视为重叠区间。

核心： 还是一样进行排序，不过它的输出时从小到大，则意味着我们需要从小到大进行排序，之后进行对应的处理，具体如下：

class Solution {
public:static bool cmp (const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {//核心思想：贪心问题，本质就是看最大的区间能包含几个//处理方法：先左边的从大到小排，将一个元素放入result中//若果result的尾部的元素右端点大于等于intervals[i]的左端点，那么进行合并，右端点选择二者大的那个元素//否则代表无法合并，就将它放入result中bool flag=false;//用来记录是否合并，如果没合并直接返回原vectorvector<vector<int>> result;sort(intervals.begin(),intervals.end(),cmp);//从小到大进行排序result.push_back(intervals[0]);//先放第一个元素for(int i=1;i<intervals.size();i++){if(result.back()[1]>=intervals[i][0]){//能合并的情况，右边元素大于下一个元素的左边元素flag=true;result.back()[1]=max(intervals[i][1], result.back()[1]);//选择最大的右端点}else{result.push_back(intervals[i]);}}//感觉下面有点多余，其实可以直接返回resultif(!flag){//代表没有合并的情况return intervals;}else{//合并的情况return result;}}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！