LC56. 合并区间

标签：end 边界 int 合并 start LC56 intervals 区间

题目来源于力扣题库，题目链接：LC56.合并区间

Q：以数组 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] 可被视为重叠区间。

提示：

　　1 <= intervals.length <= 104
　　intervals[i].length == 2
　　0 <= start_i <= end_i <= 104

A：思路：

　　第一步，排序。排序是为了使得相邻的区间尽可能的挨着，为了后续的左或右边界的比较，这里根据左边界或右边界进行排序都可，笔者这里按照左边界进行升序排序。 　　第二步，比较。将intervals[0]作为一个初始基准，从第二个开始比较，记start为待放入结果集的初始左边界，即start = intervals[0][0]，同理待放入结果集的右边界为end = intervals[0][1]； 　　接着，从intervals[i](i∈[1, intervals.length - 1])开始跟前一个区间进行比较，假设i = 1，也就是说intervals[1]和intervals[0]进行比较，观察一下两个区间[start, end] 和[intervals[1][0], intervals[1][1]]，它们是排序后的，故一定有start < intervals[1][0]，也就是说待放入结果集的左边界一定是确定的，也就是start； 　　那么如何待放入结果集的右边界呢？ 　　由于end和intervals[1][0]的大小关系是不确定的，可大可小，所以此时就分为了两种情况： 　　若intervals[1][0] > end，表示不会出现重合区间，直接将[start, end]加入结果集即可，并更新下一次的start和end。 　　若intervals[1][0] < end，表示会出现重合，则更新end即可。 　　循环至终，也要记得将最后的[start, end]加入结果集。

　　以下是Java代码，仅供参考：

 

package algo;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class mergeSolution_56{
    public int[][] merge(int[][] intervals){

        if(intervals.length == 1) return intervals; // 如果题目给出的二维数组长度为1，则不需要合并，直接返回intervals

        Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0])); // 现将多个区间按照其左边界排序，这样可以简化问题

        List<int[]> res = new LinkedList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];

        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] > end){ // 不重合,说明该区间不需要与后面的区间进行比较了，即其为结果之一，加入结果集即可
                res.add(new int[]{start, end}); // 加入当前的 [start, end] 区间
                start = intervals[i][0]; // 更新start
                end = intervals[i][1]; // 更新end
            }else{
                end = Math.max(end, intervals[i][1]); // 重合，更新右边界
            }
        }
        res.add(new int[]{start, end});
        return res.toArray(new int[res.size()][]);
    }


    /* 测试 */
    public static void main(String[] args) {
        mergeSolution_56 solution_56 = new mergeSolution_56();
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] answer = solution_56.merge(intervals);
        for (int[] is : answer) {
            System.out.println(Arrays.toString(is));
        }
    }
}

 

标签：end,边界,int,合并,start,LC56,intervals,区间
From： https://www.cnblogs.com/fxy0715/p/17444491.html