[LeetCode/LintCode] Merge Intervals

gougoujiang 發(fā)布于2019-08-14 15:16 / 1902人閱讀

摘要：方法上沒太多難點(diǎn)，先按所有區(qū)間的起點(diǎn)排序，然后用和兩個(gè)指針，如果有交集進(jìn)行操作，否則向后移動(dòng)。由于要求的，就對(duì)原數(shù)組直接進(jìn)行操作了。時(shí)間復(fù)雜度是的時(shí)間。

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

方法上沒太多難點(diǎn)，先按所有區(qū)間的起點(diǎn)排序，然后用pre和cur兩個(gè)指針，如果有交集進(jìn)行merge操作，否則pre向后移動(dòng)。由于要求O(1)的space，就對(duì)原數(shù)組直接進(jìn)行操作了。
時(shí)間復(fù)雜度O(nlogn)是Collections.sort()的時(shí)間。for循環(huán)是O(n)。
這道題有兩個(gè)點(diǎn)：
學(xué)會(huì)使用Collections.sort(object, new Comparator(){})進(jìn)行排序;
對(duì)于要進(jìn)行更改的數(shù)組而言，其一，for循環(huán)不要用for (a: A)的形式，會(huì)出現(xiàn)ConcurrentModificationException的編譯錯(cuò)誤，文檔是這樣解釋的：it is not generally permissible for one thread to modify a Collection while another thread is iterating over it. 其二，對(duì)intervals的cur元素進(jìn)行刪除操作之后，對(duì)應(yīng)的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;
    }
}