56. 合并区间 #

以数组 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,(arr1,arr2)->{
            if(arr1[0]==arr2[0]){
                return arr1[1]-arr2[1];
            }else{
                return arr1[0]-arr2[0];
            }
        });
        List<int[]> res=new ArrayList<>();
        res.add(new int[]{intervals[0][0],intervals[0][1]});
        for(int i=1;i<intervals.length;i++){
            int[] temp=res.get(res.size()-1);
            int[] nowItem=intervals[i];
            if(nowItem[0]>=temp[0]&&nowItem[0]<=temp[1]){
                temp[0]=Math.min(nowItem[0],temp[0]);
                temp[1]=Math.max(nowItem[1],temp[1]);
            }else{
                res.add(nowItem);
            }
        }
        int n=res.size();
        int[][] ans=new int[n][];
        for(int i=0;i<n;i++){
            ans[i]=res.get(i);
        }
        return ans;
    }
}

实际上，左端点不用判断，因为已经按照从小到大的顺序进行排序过了

复杂度分析 #

时间复杂度：O(nlogn)，其中 n 是 intervals 的长度。瓶颈在排序上。
空间复杂度：O(1)。排序的栈开销和返回值不计入。