区间合并的问题 leetcode 56

总体思路：先把数组按照第一个元素的大小升序排序，将第一个元素加入到目标列表中
按顺序遍历其他元素
按如下操作：

1. 若该元素的首位大于当前元素的末位， 则新建一个区间，加入目标列表
2. 判断该元素的末位和当前元素的末位，取其最大值， 更新该区间的末位

class Solution {
    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        // 先判断只有一个 或者没有的情况
        if (len < 2) {
            return intervals;
        }

        // 按照起点排序
        // intervals.sort(Comparator.comparingInt(o -> o[0]));
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

        // 也可以使用 Stack，因为我们只关心结果集的最后一个区间
        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);

        for (int i = 1; i < len; i++) {
            int[] curInterval = intervals[i];

            // 每次新遍历到的列表与当前结果集中的最后一个区间的末尾端点进行比较
            int[] peek = res.get(res.size() - 1);
            // 如果当前遍历到的元素的第一位大于已存在的末位
            if (curInterval[0] > peek[1]) {
                //新建一个区间
                res.add(curInterval);
            } else {
                // 注意，这里应该取最大
                peek[1] = Math.max(curInterval[1], peek[1]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}