Leetcode 56. 合并区间

力扣传送门(opens new window)

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

解题思路：

1. 首先，将区间集合按照区间的起始位置进行排序，这样可以方便后续的处理。
2. 创建一个结果集合，用于存储合并后的区间。
3. 遍历排序后的区间集合，逐个比较当前区间与前一个区间的关系。
4. 如果当前区间的起始位置大于前一个区间的结束位置，即当前区间与前一个区间不重叠，说明当一个区间可以直接添加到结果集合中。
5. 如果当前区间的起始位置小于等于当前区间的结束位置，说明两个区间存在重叠。
6. 在这种情况下，更新当前区间的结束位置为两个区间结束位置的较大值，以确保包含重叠区间的所有元素。
7. 继续遍历下一个区间，重复步骤4和步骤5，直到遍历完所有的区间。
8. 最后，返回结果集合即为合并后的区间集合。

代码实现：

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length == 0){
            return new int[0][0];
        }   
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
        List<int[]> list = new ArrayList();
        int pre = intervals[0][0];
        for(int i = 1;i < intervals.length;i++){
             if(intervals[i][0] > intervals[i-1][1]){
                list.add(new int[]{pre,intervals[i-1][1]});
                pre = intervals[i][0];
            }else{
                intervals[i][1] = Math.max(intervals[i][1],intervals[i-1][1]);
            }
        }

        list.add(new int[]{pre,intervals[intervals.length-1][1]});
        return list.toArray(new int[list.size()][]);
    }
}