【LeetCode】Day37-合并区间

56. 合并区间【中等】

先将区间排序，然后合并重叠区间，思路还是挺清晰的

一些实现不会写，比如二维数组按首元素排序（Arrays.sort），List转int[]（.toArray），访问List中元素（.get），返回空数组（return new int[0][]）等等

class Solution {
    public int[][] merge(int[][] intervals) {
        int n=intervals.length;
        //二维数组排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                //如果第一个数字相同,按第二个数字升序排列
                if(o1[0]==o2[0])
                    return o1[1]-o2[1];
                //按第一个数字升序排列
                return o1[0]-o2[0];
            }
        });
        //合并区间
        List<int[]>merged=new ArrayList<>();
        merged.add(new int[]{intervals[0][0],intervals[0][1]});
        for(int i=1;i<n;i++){
            int start2=intervals[i][0];
            int end1=merged.get(merged.size()-1)[1],end2=intervals[i][1];
            //有重叠
            if(end1>=start2)
                merged.get(merged.size()-1)[1]=Math.max(end1,end2);//修改上一个merged区间的末尾值
            //无重叠
            else
                merged.add(new int[]{start2,end2});//添加intervals区间
        }
        //List转换为int[][]返回
        return merged.toArray(new int[0][]);
    }
}

时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)，只需一次遍历时间复杂度O(n)，O(nlogn)是排序所需的时间复杂度

空间复杂度： O ( l o g n ) O(logn) O(logn)，排序的空间复杂度（存储结果不计入空间复杂度）