56. Merge Intervals

Leetcode Array Sort

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

分析

合并区间。将区间排序，然后依次检查相邻间隔是否重叠，如果重叠，那么就删去重叠的部分。区间排序顺序由区间的开始位置决定，如果该区间的开始位置，大于上一个区间的结束位置，那么区间肯定是不重叠的，将该区间加入到结果中；否则，肯定发生重叠，要去除重叠的部分：如果该区间包含在上一个区间中，即这个区间的结束位置小于上个区间的结束位置，则结果保持不变；否则，更新上个区间的结束位置为该区间的结束位置。

 public List<Interval> merge(List<Interval> intervals) {
    if (intervals == null || intervals.size() == 0) return intervals;
    intervals.sort(Comparator.comparing(a->a.start));
    LinkedList<Interval> merged = new LinkedList<>();
    merged.add(intervals.get(0));
    for (Interval interval: intervals.subList(1, intervals.size()))
        if (merged.getLast().end < interval.start) merged.add(interval);
        else if (merged.getLast().end < interval.end) merged.getLast().end = interval.end;
    return merged;
}