Leetcode 56 合并区间

题意理解：???????

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

? ? ? ? 目标：合并所有重叠区间，则原有区间的右边界可能发生变化。

解题思路：

? ? ? ? 采用贪心探索每个独立区间的最右区间。

? ? ? ? 首先，要识别重叠的区间，用于后续处理。按照每个区间的左边界升序排序。

? ? ? ? 当且仅当，（i-1区间的右边界）>=（i区间的左边界），即为i区间和i-1区间重叠。

? ? ? ? 识别出重叠区间后，对最左区间的右边界进行探索，获得两区间合并后的最远右边界。

? ? ? ?以此完成区间合并——获得一个新区间。

????????

? ? ? ? 若区间无重叠现象，则直接作为一个独立区间加入结果集。

????????

1.贪心解题

明确全局最优解: 划分独立的区间。局部最优解：尽可能延长重叠区域的右区间。

为鉴别重叠区域，首先按照左边界升序排序。

对于重叠的区域总是更新合理的右边界。

将合并后的新区间及独立的老区间加入结果集。

注意：List转数组：

方法一：

int[][] resultArr=new int[result.size()][2];
for(int i=0;i<result.size();i++) resultArr[i]=result.get(i);

方法二：

res.toArray(new int[res.size()][]);

public int[][] merge(int[][] intervals) {
        //按照左边界升序排序
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        //记录结果集
        LinkedList<int[]> result = new LinkedList<>();
        result.add(intervals[0]);
        for(int i=1;i<intervals.length;i++){
            //有重叠，更新右边界
            if(intervals[i-1][1]>=intervals[i][0]){
                intervals[i][1]=Math.max(intervals[i-1][1],intervals[i][1]);
                result.getLast()[1]=intervals[i][1];
            }else{
                //无重叠，加入新区间
                result.add(intervals[i]);
            }
        }
        return  result.toArray(new int[result.size()][]);
    }

2.分析?

时间复杂度：O(n logn) 主要的时间耗费是排序和遍历数组。

空间复杂度：O(logn) 主要的空间耗费是排序所需的额外空间。