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<ObjectType>(){})进行排序; 对于要进行更改的数组而言，其一，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;    }}