合并区间

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

 

示例 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] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

1. 按照第二个元素从小到大排序。
2. 如果左边元素的第二个值大于右边元素的第一个值，那么存在交叉，修改右边的元素，扩大区间。
3. 凑出返回值。

时间复杂度 O(n*n)
空间复杂度 O(n)

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {//按照第二个元素排序
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        boolean[] isDelete = new boolean[intervals.length];//改元素是否在原数组中删除
        int deleteNum = 0;
        for (int i = 0; i < intervals.length; i++) {
            for (int j = i + 1; j < intervals.length; j++) {
                if (intervals[i][1] >= intervals[j][0]) {//如果存在区间交叉
                    int first = Math.min(intervals[i][0], intervals[j][0]);
                    int second = Math.max(intervals[i][1], intervals[j][1]);
                    intervals[j][0] = first;//修改后面的那个（j），这样就可以保证后面的那个可以继续与更后面的比较
                    intervals[j][1] = second;
                    isDelete[i] = true;
                    deleteNum++;
                    break;
                }
            }
        }
        //因为是在原来的数组基础上修改的，因此要凑出返回值
        int left = intervals.length - deleteNum;
        int res[][] = new int[left][2];
        int index = 0;
        for (int i = 0; i < intervals.length; i++) {
            if (!isDelete[i]) {
                res[index] = intervals[i];
                index++;
            }
        }

        return res;
    }
}

官方题解按照第一个值排序

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

参考文献

官方题解

赏

谢谢你请我吃糖果

微信