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()][]);
    }