每天一道leetcode56-合并区间

乔戈里

发布于 2019-09-17 14:55:58

3030

发布于 2019-09-17 14:55:58

文章被收录于专栏：Java那些事

题目

每天一道leetcode56-合并区间分类：数组中文链接： https://leetcode-cn.com/problems/merge-intervals/description/ 英文链接 https://leetcode.com/problems/merge-intervals/description/

题目详述

给出一个区间的集合，请合并所有重叠的区间。示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

题目详解

思路

首先根据数组中的第一个数字进行排序，[1,3][2,6][8,10]中的就是1,2,8根据这三个数字对二维数组中进行排序
排完序以后，这样二维数组中的数组就按照第一个数字的大小进行了排序，所以第一个数字是依次递增的
然后就去比较[1,3]中3与下一个数组中2和6比较大小，如果数字3在2和6之间说明这两个数组是可以合并的；合并完是[1,6]
[1,6]继续与[8,10]合并，比较6与8,10，6是小于8的所以这个时候不能合并，只能二维数组的下标i进行i++的操作
这个还有一种情况就是比如是[1,10]与[2,8],10是大于8的这个时候，也可以进行合并
把这三种情况讨论一遍进行

代码

class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
  }


public List<Interval> merge(List<Interval> intervals) {
    Collections.sort(intervals, new Comparator<Interval>() {
        @Override
        public int compare(Interval o1, Interval o2) {
            if(o1.start > o2.start)
                return 1;
            else if(o1.start < o2.start)
                return  -1;
            else
                return 0;
        }
    });
    int i = 0;
    while(i < intervals.size())
    {
        if(i != intervals.size() - 1)
        {
            if(intervals.get(i).end >= intervals.get(i+1).start && intervals.get(i).end <= intervals.get(i+1).end)
            {
                int tempStart = intervals.get(i).start;
                int tempEnd = intervals.get(i+1).end;
                intervals.remove(i);
                intervals.get(i).start = tempStart;
                intervals.get(i).end = tempEnd;
            }else if(intervals.get(i).end < intervals.get(i+1).start){
                i++;
            }else if(intervals.get(i).end > intervals.get(i+1).end){
                intervals.remove(i+1);
                i=i;
            }
        }else {
            i++;
        }
    }
    return intervals;
}

代码讲解

10-20行就是根据第一个数字来进行排序
26行-32行就是去比较 [1,3] [2,6]（分别代表intervals.get(i) 和intervals.get(i+1)）中3满足了>=2 且 <= 6 然后就进行合并
33-34行就是[1,3] [5,7]中3 < 5了无法进行合并，i++
35-37行就是[1,10] [2,8] 中 10大于8也可以合并（看到这里，你可能会有疑问为啥可以合并了，因为我们在10-20行已经根据第一个数字排序过了，所以前后两个数组中[a,3],[b,7]比如说这个，a是必然小于等于b的）
39-40行，最后一个元素，直接i++

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2018-11-13，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法