[Leetcode] Merge Intervals and Insert Interval 合并间

antyiwei 发布于2019-08-14 12:33 / 2594人阅读

摘要：我们只要把所有和该有重叠的合并到一起就行了。最后把前半部分的列表，合并后的大和后半部分的列表连起来，就是结果了。

Merge Intervals 最新更新请见 https://yanjia.me/zh/2019/02/...

Given a collection of intervals, merge all overlapping intervals.For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

排序法 复杂度

时间 O(NlogN) 空间 O(N)

思路

首先根据Interval的起点，我们将其排序，这样能合并的Interval就一定是相邻的了：

[1,3] [5,6] [2,3]
---> [1,3] [2,3] [5,6]

然后我们就顺序遍历这个列表，并记录一个当前待合并的Interval，如果遍历到的Interval和当前待合并的Interval有重复部分，我们就将两个合并，如果没有重复部分，就将待合并的Interval加入结果中，并用新的Interval更新这个待合并的Interval。因为数组已经排过序，前面的Interval的起点肯定小于后面Interval的起点，所以在判断是否有重叠部分时，只要考虑待合并的Interval的终点和遍历到的Interval的起点的关系就行了。

注意

判断重叠的边界时包含等于的情况

循环后还要把最后一个待合并的Interval也加入结果中

更新待合并Interval的边界时，要同时更新起点和终点

代码

public class Solution {
    public List merge(List intervals) {
        List res = new LinkedList();
        if(intervals.size() == 0){
            return res;
        }
        // 按照起点排序
        Collections.sort(intervals, new Comparator(){
            public int compare(Interval i1, Interval i2){
                return i1.start - i2.start;
            }
        });
        // 拿出第一个待合并的Interval
        Interval curr = intervals.get(0);
        for(Interval itv : intervals){
            // 如果有重叠部分，更新待合并的Interval的起点和终点
            if(curr.end >= itv.start){
                curr.start = Math.min(curr.start, itv.start);
                curr.end = Math.max(curr.end, itv.end);
            } else {
            // 否则将待合并的Interval加入结果中，并选取新的待合并Interval
                res.add(curr);
                curr = itv;
            }
        }
        // 将最后一个待合并的加进结果
        res.add(curr);
        return res;
    }
}

Insert Interval 最优解请见：https://yanjia.me/zh/2019/02/...

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).You may assume that the intervals were initially sorted according to their start times.
Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

排序法 复杂度

时间 O(NlogN) 空间 O(N)

思路

和Merge Interval的思路接近，这题中我们只有一个待合并的Interval，就是输入给出的。我们只要把所有和该Interval有重叠的合并到一起就行了。为了方便操作，对于那些没有重叠部分的Interval，我们可以把在待合并Interval之前的Interval加入一个列表中，把之后的Interval加入另一个列表中。最后把前半部分的列表，合并后的大Interval和后半部分的列表连起来，就是结果了。

注意

因为待合并的Interval出现的位置不确定，判断重叠与否时既要判断起点，也要判断终点

原列表为空时，直接加入待合并的Interval后返回

代码

public class Solution {
    public List insert(List intervals, Interval newInterval) {
        List before = new LinkedList();
        List after = new LinkedList();
        List res = new LinkedList();
        if(intervals.size() == 0){
            res.add(newInterval);
            return res;
        }
        // 排序
        Collections.sort(intervals, new Comparator(){
            public int compare(Interval i1, Interval i2){
                return i1.start - i2.start;
            }
        });
        for(Interval itx : intervals){
            // 将待合并Interval之前的存入一个列表中
            if(newInterval.start > itx.end){
                before.add(itx);
            }
            // 将有重叠的Interval都合并起来
            if((newInterval.end >= itx.start && newInterval.end <= itx.end) || (newInterval.start <= itx.end && newInterval.start >= itx.start)){
                newInterval.start = Math.min(newInterval.start, itx.start);
                newInterval.end = Math.max(newInterval.end, itx.end);
            }
            // 将待合并Interval之后的存入一个列表中
            if(newInterval.end < itx.start){
                after.add(itx);
            }
        }
        // 把三部分加起来
        res.addAll(before);
        res.add(newInterval);
        res.addAll(after);
        return res;
    }
}

云服务器 GPU云服务器 Intervals Interval LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64554.html

leetcode57. Insert Interval

摘要：题目要求给定一组顺序排列且相互之间没有重叠的区间，输入一个区间，将它插入到当前的区间数组中，并且将需要合并的区间合并，之后返回插入并且合并后的区间。我们将这三个类型的区间分别标注为类型，类型，类型。题目要求 Given a set of non-overlapping intervals, insert a new interval into the intervals (merge...

Yuanf 2019-08-16 10:37 评论0 收藏0
leetcode--57--Insert Interval

摘要：问题描述分析这道题的关键在于理解问题，抽取原型，理解中间可以部分如何界定，以及非部分如何进行追加。需要注意的是循环到最后一个元素和在最后一个元素的区别。问题描述： Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You m...

kycool 2019-07-31 11:04 评论0 收藏0
leetcode56 Merge Intervals

摘要：题目要求输入一系列区间，将出现交叉的区间合并起来，并将合并后的区间返回。将这两个数组分别排序可以得到和。也就是说，合并后的结果和是等价的。举个栗子，输入为，先判断是否是独立区间，可见可以和合并，则将修改为。题目要求 Given a collection of intervals, merge all overlapping intervals. For example, Given...

shmily 2019-08-16 10:37 评论0 收藏0
[LeetCode] Insert Interval

Problem Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times....

Jonathan Shieber 2019-08-19 11:08 评论0 收藏0
[LeetCode/LintCode] Merge Intervals

摘要：方法上没太多难点，先按所有区间的起点排序，然后用和两个指针，如果有交集进行操作，否则向后移动。由于要求的，就对原数组直接进行操作了。时间复杂度是的时间。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...

gougoujiang 2019-08-14 15:16 评论0 收藏0