LeetCode56 . Merge Intervals

题目:

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].

题目的大意是将有重叠的区间合并为一个大区间
直接上代码：

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new LinkedList<>();
        if(intervals.size()==0)
            return res;
        //这里使用了lamdba写法，先按起始位进行排序
        intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for(Interval inte : intervals){
            if(inte.start<=end){
                end = Math.max(end,inte.end);
            }else{
                res.add(new Interval(start,end));
                start = inte.start;
                end = inte.end;
            }
        }
        
        res.add(new Interval(start,end));
        return res;
    }
}

解法可分为几个步骤：

• 先对每个区间按起始位置的的大小从小到大进行排序(这步处理很重要)
• 对排序好的区间进行遍历，此时要维护一个扩展区间，当此扩展区间与当前遍历到的小区间不能合并时，则将它加入结果列表。扩展区间用 [start,end] 来表示,当前遍历到的区间用inte表示。如何判断扩展区间能否继续扩展？我们可以比较当前区间的起始位inte.start 是否小于等于 扩展区间的end，如果是则继续扩展。