By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、合并区间

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

示例 1:

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

示例 2:

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

1.1、解题思路

先排序，在看代码

1.2、算法

public int[][] merge(int[][] intervals) {
    // 先按照区间起始位置排序
    Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
    // 遍历区间
    int[][] res = new int[intervals.length][2];
    int idx = -1;
    for (int[] interval: intervals) {
        // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
        // 则不合并，直接将当前区间加入结果数组。
        if (idx == -1 || interval[0] > res[idx][1]) {
            res[++idx] = interval;
        } else {
            // 反之将当前区间合并至结果数组的最后区间
            res[idx][1] = Math.max(res[idx][1], interval[1]);
        }
    }
    return Arrays.copyOf(res, idx + 1);
}

1.3、测试

@Test
public void test(){
    int[][]  intervals = {
        {1, 3},
        {2, 6},
        {8, 10},
        {15, 18}
    };
    // int[][]  intervals = {
    //         {1, 4},
    //         {4, 5},
    // };
    // int[][]  intervals = {
    //         {1, 4},
    //         {0, 0},
    // };
    merge(intervals);
}

​

ContactAuthor