2021/2/1 合并区间

题目描述

给出一组区间，请合并所有重叠的区间。

示例

输入

[[10,30],[20,60],[80,100],[150,180]]

返回值

[[10,60],[80,100],[150,180]]

解题思路

1. 按照 start 值从小到大排序
2. 遍历所有元素，后一个元素的 start 比前一个的 end 还要小，则比较后一个的 end 和前一个的 end 哪个更大，最大的那个 end 值赋给前一个元素的 end，并删除后一个元素。

王清楚大大的博客《【牛客题霸题解】合并区间》 已经给出了很生动形象的思路，在这里偶就不多卖弄了，不过有一个点需要注意：

这时候 20 小于 50，不能用 20 去替换前一个的 end。

Java代码实现

public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if (intervals == null || intervals.size() < 2) return intervals;
        // 排序，start 值从小到大；start 值相同则按照 end 从小到大排序
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare (Interval o1, Interval o2) {
                if (o1.start == o2.start) {
                    return o1.end - o2.end;
                } else {
                    return o1.start - o2.start;
                }
            }
        });

        // 获得 intervals 的迭代器，对 intervals 本身进行操作
        Iterator<Interval> it = intervals.iterator();
        Interval prev = it.next();
        while (it.hasNext()) {
            Interval current = it.next();
            // 若遍历到的 start 比前一个的 end 小
            if (current.start <= prev.end) {
                // 前一个元素的 end 赋最大那一个值
                prev.end = prev.end > current.end ? prev.end : current.end;
                it.remove();
            } else {
                prev = current;
            }
        }
        return intervals;
    }
}