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

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