题解 | #合并区间#

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) {
        if (intervals.size() == 0) return intervals;
        
        //首先要做一件重要的事情，就是先把输入进来的空间，按照左端点排序
        //这里利用了匿名内部类的形式，重写了compare方法
        //之前我用的是Ayyays的sort方法重写，但是它接收的参数应该是数组类型，ArrayList应该用Collection的sort方法
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval i1, Interval i2) {
                return Integer.compare(i1.start, i2.start);
            }
        });
        ArrayList<Interval> res = new ArrayList<>();
        res.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
            Interval interval = intervals.get(i);
            Interval preInterval = res.get(res.size() - 1);
            if (interval.start > preInterval.end ) {
                res.add(interval);
            } else if (interval.start <= preInterval.end) {
                //这里其实包含了两种情况，都是有重叠的，需要合并区间
                //可能是当前区间完全在之前的区间里面
                //也可能需要把之前的区间更改一下，增大区间范围
                preInterval.end = Math.max(preInterval.end, interval.end);
                res.set(res.size() - 1, preInterval);
            }

        }
        return res;


    }
}

首先一点很重要，就是直接对输入的区间，按照左端点进行排序。这里利用了匿名内部类进行定义排序。细节地方，如果区间为空，直接输出，这里我一开始没有注意，造成了程序报错，索引越界问题。在合并区间的时候，需要考虑是否有重叠部分，重叠部分也分为两种情况，一种是需要更改原区间，一种不做任何操作，可以把他们合并起来。