[LeetCode/LintCode] Merge Intervals

gougoujiang 發布于2019-08-14 15:16 / 1898人閱讀

摘要：方法上沒太多難點，先按所有區間的起點排序，然后用和兩個指針，如果有交集進行操作，否則向后移動。由于要求的，就對原數組直接進行操作了。時間復雜度是的時間。

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;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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