算法 26 Merge Intervals

题目：给一个区间集，合并有重叠的区间。

例如：给出区间 [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

思路：首先需要区间集有序，按照每个区间的开始值排序升序。然后遍历比较，若前一个区间的end值大于后一个区间的start值，比较两区间end值，取较大的合并两区间，之后依次类推。

代码：

static List<Interval> merge(List<Interval> intervals) {
    //若区间为0~1个，直接返回
    if (intervals.size() <= 1)
        return intervals;
    //按 start 元素排序
    intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));

    List<Interval> result = new LinkedList<Interval>();
    int start = intervals.get(0).start;
    int end = intervals.get(0).end;
    for (Interval interval : intervals) {
        if (interval.start <= end)
            // 重叠时,对end进行处理
            end = Math.max(end, interval.end);
        else {
            // 添加上一个分好的区间,并重置边界
            result.add(new Interval(start, end));
            start = interval.start;
            end = interval.end;
        }
    }

    // 添加
    result.add(new Interval(start, end));
    return result;
}

时间复杂度：O(nlogn)
空间：O(n)