​LeetCode刷题实战56:合并区间

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 合并区间,我们先来看题面:

https://leetcode-cn.com/problems/merge-intervals/

Given a collection of intervals, merge all overlapping intervals.

题意

给出一个区间的集合,请合并所有重叠的区间。

样例

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

解题


此题的难点就是判断哪些区间重叠了,以及如何进行合并。重叠只有两种情况,一个区间是另外一个区间的子集,或者两个区间相邻(有部分重叠)。由于有区间在容器中有次序关系,那么需要分a是b的子集还是b是a的子集,则重叠的情况就分为了四种。那能不能找到一种操作,在合并之前就将所有的情况合并为一种情况呢?答案显然是有的——排序。此处的排序需要以左区间为主次序递增,右区间为辅次序递增。即首先保证左区间递增,如果某两个元素的左区间相同,那么则比较他们的右区间。排序后再进行合并即可。
示例图解

class Solution {
public:
  static bool myCompare(Interval one, Interval two){
    //以start为主次序递增
    if (one.start == two.start){//当start相等的时候,才进行比较end
      return one.end < two.start;
    }
    else {//否则直接比较start的大小关系
      return one.start < two.start;
    }
  }

vector<Interval> merge(vector<Interval>& intervals) {
    sort(intervals.begin(), intervals.end(), myCompare);//按照自定义顺序进行排序
    for (int i = 0; i < intervals.size(); ++i){//动态扫描
      int begin = intervals[i].start;//基准begin
      int end = intervals[i].end;//基准end
      //因为排序的时候就保证了start为主次序递增,只要下一个的start小于上一个的end,就证明可以进行合并
      while (i + 1 < intervals.size() && intervals[i + 1].start <= end){//如果能进行合并
        end = max(intervals[i + 1].end, end);//更新
        intervals.erase(intervals.begin() + i + 1);
      }
      intervals[i].end = end;//更新i的end
    }
    return intervals;
  }
};

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

上期推文:

LeetCode1-50题汇总,速度收藏!
LeetCode刷题实战51:N 皇后
LeetCode刷题实战52:N皇后 II
LeetCode刷题实战53:最大子序和
LeetCode刷题实战54:螺旋矩阵
LeetCode刷题实战55:跳跃游戏
(0)

相关推荐