NC37 合并区间

题目链接：https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a

题目描述

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

请保证合并后的区间按区间起点升序排列。

数据范围：区间组数 0 ≤n≤2×10^5，区间内 的值都满足 0≤val ≤2×10^5

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

进阶：空间复杂度 O(val)，时间复杂度O(val)

示例 1：

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

示例 2：

输入：[[0,10],[10,20]]
返回值：[[0,20]]

解题代码

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) {
        ArrayList<Interval> res = new ArrayList<>();
        //去除特殊情况
        if (intervals.size() == 0)
            return res;
        //重载比较，按照区间首排序
        intervals.sort((o1, o2) -> {
            if (o1.start != o2.start)
                return o1.start - o2.start;
            else
                return o1.end - o2.end;
        });
        //放入第一个区间
        res.add(intervals.get(0));
        int count = 0;
        //遍历后续区间，查看是否与末尾有重叠
        for (int i = 1; i < intervals.size(); i++) {
            Interval o1 = intervals.get(i);
            Interval origin = res.get(count);
            if (o1.start > origin.end) {
                res.add(o1);
                count++;
                //区间有重叠，更新结尾
            } else {
                res.remove(count);
                Interval s = new Interval(origin.start, o1.end);
                if (o1.end < origin.end)
                    s.end = origin.end;
                res.add(s);
            }
        }
        return res;
    }
}