合并区间

题目内容：给出一组区间，请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列。很好理解，就是将给定区间中相交的区间进行合并，并且按照起点进行升序排列。

例子：

输入：[[10,30],[20,60],[80,100],[150,180]]

返回值：[[10,60],[80,100],[150,180]]

在做之前我们先思考一下，需要合并区间的情况有多少种（待扩张区间：我们将选中区间与该区间进行合并；选中区间：当前选取的区间）：

• 待扩张区间与选中区间起点重合
  • 选中区间的结束点 <= 待扩张区间终点，这种情况说明待扩张区间的范围要大于选中区间，因此不需要进行处理。
  • 选中区间的结束点>待扩张区间终点，这种情况，需要将选中区间与待扩张区间进行合并，由于起点是重合的，因此只需要将待扩张区间的结束点修改为选中区间的结束点即可。
• 待扩张区间与选中区间起点不重合（这里指选中区间的起点均大于等于待扩张区间）
  • 选中区间的起点和终点 <= 待扩张区间的结束点，即选中区间被包含在待扩张区间内。
  • 选中区间的起点在待扩张区间的终点前，但选中区间的终点在区间的终点后。
  • 选中区间的起点等于待扩张区间的终点，即两个区间刚好接壤。
  • 选中区间的起点大于待扩张区间的终点，即两个区间不相交。

上面的条件看起来可能比较抽象，并且不易于理解，我们通过下面这张图来直观地体会上述条件，图中两条线中上面为待扩张区间，下面为选中区间。（橙色的线是为了让线看起来没那么难受-_-||，今后的文章中，我将会使用PPT来画图、制作动画进行解析）

由图可见，起点相同的情况只有第三种需要进行合并，起点不同的情况只有第三、四种需要进行合并，第五种则将选中区间作为下一个待扩张区间。除此之外，由于原给定区间是无序的，处理起来不是很方便，我们需要以区间的起点进行排序，再做后续的合并操作。代码如下：

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) {
        Collections.sort(intervals, (o1, o2) -> {
            return o1.start - o2.start;
        });
        Deque<Interval> queue = new LinkedList<>();
        for(int i = 0; i < intervals.size(); i++) {
            if(queue.isEmpty()) {
                queue.offer(intervals.get(i));
            } else {
                Interval itv = queue.peekLast();
                Interval interval = intervals.get(i);
                if(itv.start == interval.start) {
                    itv.end = Math.max(itv.end, interval.end);
                } else {
                    if(itv.end < interval.start) { // 两个区间不相交
                        queue.offer(interval);
                    } else {
                        itv.end = Math.max(interval.end, itv.end);
                    }
                }
            }
        }
        return new ArrayList<>(queue);
    }
}

我们将第一个区间作为待扩张区间，接下来将剩余的区间都与待扩张区间进行比对，将满足条件的区间融入待扩张区间，完成合并操作。由于预先进行了排序处理，因此所有后面的区间的起点均大于等于前面的起点，这样处理起来就非常方便了。当起点重合时，将待扩张区间的终点值设置为两个区间中最大值即可。起点不重合时，看看两者是否相交，不相交则将该区间作为下一个待扩张区间；相交则将待扩张区间的终点值设置为两个区间中最大值。