区间合并

1、问题描述

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

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

2、解题思路

我们按照区间的左端点进行排序，让这些区间尽可能的挨在一起。
然后我们的基本想法是看前面区间的右端点是否大于后边区间的左端点，如果是，说明发生了区间重叠。

3、代码实现

这里参考了LeetCode56 和代码随想录的题解。

//合并区间
public class LeetCode56 {
    public static int[][] merge(int[][] intervals) {
        LinkedList<int[]> res=new LinkedList<>();
        //按照左边界排序
        Arrays.sort(intervals,(x1,x2)->Integer.compare(x1[0],x2[0]));
        //第一个区间可以先放进去，如果后面重叠，在res上面直接合并
        res.add(intervals[0]);
        //其实我们res中的最后一个区间的右边界相当于当前的最大右边界了
        //如果后面遍历的区间左端点小于整个最大右边界，说明区间重叠，需要合并
        //否则直接加入res就行
        for (int i = 1; i <intervals.length; i++) {
            if(intervals[i][0]<=res.getLast()[1]){  //区间重叠
                int start=res.getLast()[0];
                int end=Math.max(intervals[i][1],res.getLast()[1]);
                //删除res最后一个结点
                res.removeLast();
                //将合并后的区间加入res
                res.add(new int[]{start,end});
            }else{
                //没发生重叠直接加入就行
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }

    public static void main(String[] args) {
        int[][] intervals={
                {1,3},
                {2,6},
                {8,10},
                {15,18}
        };
        int[][] merge = merge(intervals);
        Arrays.stream(merge).forEach(x->{
            System.out.println(Arrays.toString(x));
        });
    }
}

去哪儿旅行手撕碰到类似的