Leetcode 56 合并区间

题意理解：

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

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

解题思路：

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

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

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

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

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

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

1.贪心解题

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

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

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

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

注意：List转数组：

方法一：

int[][] resultA服务器托管网rr=new int[result.size()][2];
for(int i=0;i

方法二：

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

public int[][] merge(int[][] intervals) {
        //按照左边界升序排序
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        //记录结果集
        LinkedList result = new LinkedList();
        result.add(intervals[0]);
        for(int i=1;i=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  res服务器托管网ult.toArray(new int[result.size()][]);
    }

2.分析

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

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

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net