【LeetCode】合并区间 Java 题解

作者：Albert

2022 年 8 月 22 日
北京
本文字数：1058 字
阅读完需：约 3 分钟

题目描述

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

示例 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] 可被视为重叠区间。 
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/merge-intervals著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是合并区间问题，题目求解的是返回一个不重叠的区间数组。题意比较容易理解，我们首先需要将输入的数组按照 intervals[i][0] 排序，使得左边界按照升序排序。当 intervals[i][0]相同时候，按照 intervals[i][1] 升序排序，方便我们比较。接着，初始化 start, end。然后动态比较每一个排序 intervals[i]。
具体实现代码如下，供参考。

通过代码

class Solution {    public int[][] merge(int[][] intervals) {        Arrays.sort(intervals, new Comparator<int[]>() {            @Override            public int compare(int[] o1, int[] o2) {                if (o1[0] != o2[0]) {                    return o1[0] - o2[0];                } else {                    return o1[1] - o2[1];                }            }        });
        List<int[]> tempAns = new LinkedList<>();        int start = -1;        int end = -1;        for (int[] interval : intervals) {            int left = interval[0];            int right = interval[1];            if (left <= end) {                end = Math.max(end,right);            } else {                if (end != -1) {                    tempAns.add(new int[]{start, end});                }                start = left;                end = right;            }        }        tempAns.add(new int[]{start, end});        int n = tempAns.size();
        int[][] ans = new int[n][];        int i = 0;        while (i < n) {            ans[i] = tempAns.get(i);            i++;        }        return ans;    }}