题解 | #合并区间#

主要思想：

• 首先将各个区间进行排序，排序规则为首先根据start进行排序，如果start相等则根据end从小到大排序
• new一个新的List result存放结果，遍历给定的intervals，比较当前interval的start是否大于result中最后一个元素的end，若大于，说明从开了一个区间，若区间有重叠，则更新result中最后一个元素的end。

import java.util.*;
/**
 * 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; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        // 首先根据start排序，如果start相等，根据end排序
        Collections.sort(intervals, (o1, o2) -> (o1.start != o2.start ? o1.start - o2.start : o1.end - o2.end));
        ArrayList<Interval> result = new ArrayList<>();
        if(intervals.size() == 0) {
            return result;
        }
        // 放入第一个区间
        result.add(intervals.get(0));
        int count = 0;
        // 遍历后续区间，查看是否与末尾有重叠
        for(int i = 1; i < intervals.size(); i++) {
            Interval o1 = intervals.get(i);
            Interval origin = result.get(result.size() - 1);
            // 如果当前Interval的start比List里面最后一个元素的end大，说明从开一个区间
            if(o1.start > origin.end) {
                result.add(o1);
            } else { // 区间有重叠，更新结尾
                if(o1.end > origin.end) {
                    result.get(result.size() - 1).end = o1.end;
                }
            }
        }
        return result;
    }
}