[LeetCode/LintCode] Merge Intervals

gougoujiang 发布于2019-08-14 15:16 / 1868人阅读

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

Problem

Given a collection of intervals, merge all overlapping intervals.

Example

Given intervals => merged intervals:

[                     [
  [1, 3],               [1, 6],
  [2, 6],      =>       [8, 10],
  [8, 10],              [15, 18]
  [15, 18]            ]
]

Challenge

O(n log n) time and O(1) extra space.

Note

方法上没太多难点，先按所有区间的起点排序，然后用pre和cur两个指针，如果有交集进行merge操作，否则pre向后移动。由于要求O(1)的space，就对原数组直接进行操作了。
时间复杂度O(nlogn)是Collections.sort()的时间。for循环是O(n)。
这道题有两个点：
学会使用Collections.sort(object, new Comparator(){})进行排序;
对于要进行更改的数组而言，其一，for循环不要用for (a: A)的形式，会出现ConcurrentModificationException的编译错误，文档是这样解释的：it is not generally permissible for one thread to modify a Collection while another thread is iterating over it. 其二，对intervals的cur元素进行删除操作之后，对应的index i要减去1。

Solution Update 2018-9

class Solution {
    public List merge(List intervals) {
        if (intervals == null || intervals.size() < 2) return intervals;
        intervals.sort((i1, i2) -> i1.start-i2.start);
        List res = new ArrayList<>();
        int start = intervals.get(0).start, end = intervals.get(0).end; //use two variables to maintain prev bounds
        for (Interval interval: intervals) {                            //iterate the interval list
            if (interval.start > end) {                                 //if current interval not overlapping with prev:
                res.add(new Interval(start, end));                      //1. add prev to result list
                start = interval.start;                                 //2. update prev bounds
                end = interval.end;
            }
            else end = Math.max(end, interval.end);                     //else just update prev end bound
        }
        res.add(new Interval(start, end));                              //add the prev which was updated by the last interval
        return res;
    }
}

in-place

class Solution {
    public List merge(List intervals) {
        if (intervals == null || intervals.size() < 2) return intervals;
        intervals.sort((i1, i2) -> i1.start-i2.start);
        Interval pre = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if (cur.start > pre.end) pre = cur;
            else {
                pre.end = Math.max(pre.end, cur.end);
                intervals.remove(cur);
                i--;
            }
        }
        return intervals;
    }
}

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

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

[Leetcode] Merge Intervals and Insert Interval 合并间

摘要：我们只要把所有和该有重叠的合并到一起就行了。最后把前半部分的列表，合并后的大和后半部分的列表连起来，就是结果了。 Merge Intervals 最新更新请见 https://yanjia.me/zh/2019/02/... Given a collection of intervals, merge all overlapping intervals.For example, Gi...

antyiwei 2019-08-14 12:33 评论0 收藏0
【LC总结】Intervals题目 (Insert/Merge/Number of Airplane

摘要：忘了这题怎么做，汗颜无地。边界用记录每个时刻的飞行数目。对于某一时刻，起飞和降落同时发生，只计算一次。先强势插入，再 Merge Intervals Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals: ...

Achilles 2019-08-14 15:50 评论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/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 评论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