合并区间

56. 合并区间 - 力扣（LeetCode）

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

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

首先将每个区间按第一个元素排序

排序之后只需要比较下一个区间的第一个元素是否大于当前区间的第二个元素

• 大于则直接加入到答案集合
• 小于或等于，则比较取两个区间第二个元素较大者加入到答案集合

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (int[] a,int[] b) -> a[0] - b[0]);//已经按第一个元素从小到大排序
        List<int[]> ans = new ArrayList<>();//存放答案的集合
        
        for(int i = 0; i < intervals.length; i++){
            //集合为空或者当前集合第一个元素大于答案集合最后一个元素，直接加入
            if(ans.isEmpty() || intervals[i][0] > ans.get(ans.size()-1)[1]){
                ans.add(new int[]{intervals[i][0], intervals[i][1]});

            }else{//当前集合第一个元素小于或等于答案集合最后一个元素
                ans.get(ans.size()-1)[1] = Math.max(intervals[i][1], ans.get(ans.size()-1)[1]);
                
            }
        }

        return ans.toArray(new int[ans.size()][]);

    }
}

时间复杂度：$O(nlog⁡n)$，其中 n为区间的数量。除去排序的开销，我们只需要一次线性扫描

空间复杂度：$O(log⁡n)$，其中 n 为区间的数量。