LeetCode-56-合并区间

题目描述：
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

在这里插入图片描述

可以使用 LinkedList，也可以使用 ArrayList。

class Solution {
    /**
     * 思路：先根据左区间将 intervals 排序，
     * 排序后遍历 intervals，将当前区间(左)和前一个区间(右)，进行比较，
     * 如果有重叠就取右区间最大的，其他没有重叠的就直接加到res中
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new LinkedList<>();
        Arrays.sort(intervals,(x,y) -> Integer.compare(x[0], y[0]));// 二维数组排序
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            // res.get(res.size()-1);// 获取res列表的最后一个元素
            if (res.get(res.size()-1)[1] >=  intervals[i][0]){// 注意是 >=
                // 合并
                res.add(new int[]{res.get(res.size()-1)[0],Math.max(res.get(res.size()-1)[1], intervals[i][1])});
                res.remove(res.size()-2);// 移除倒数第二个，也就是新加的前一个，因为已经和新加的重复了
            }else {
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);// List<int[]> -> 二维数组
    }
}