标签：二维数排序

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

示例 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] 可被视为重叠区间。

思路： 对二维数组排序，能合并则合并，无法继续合并则添加到结果组，注意最后一个区间处理；时间复杂度 O(nlogn)，其中n为区间的数量。

leetcode版本：

    public int[][] merge(int[][] intervals) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int i = 1;
        for(i = 1; i < intervals.length; i++){
            if(intervals[i][0] >= intervals[i-1][0] && intervals[i][0] <= intervals[i-1][1]){
                intervals[i][0] = intervals[i-1][0];
                intervals[i][1] = Math.max(intervals[i][1], intervals[i-1][1]);
            }
            else{
                List<Integer> lis = new ArrayList<>();
                lis.add(intervals[i-1][0]);
                lis.add(intervals[i-1][1]);
                list.add(lis);
            }
        }
        List<Integer> end = new ArrayList<>();
        end.add(intervals[i-1][0]);
        end.add(intervals[i-1][1]);
        list.add(end);
        int[][] merge = new int[list.size()][2];
        for(int j = 0; j < list.size(); j++){
            merge[j][0] = list.get(j).get(0);
            merge[j][1] = list.get(j).get(1);
        }
        return merge;
    }

本地IDE版本：

public class leetcode56 {
    public int[][] merge(int[][] intervals) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int i = 1;
        for(i = 1; i < intervals.length; i++){
            if(intervals[i][0] >= intervals[i-1][0] && intervals[i][0] <= intervals[i-1][1]){
                intervals[i][0] = intervals[i-1][0];
                intervals[i][1] = Math.max(intervals[i][1], intervals[i-1][1]);
            }
            else{
                List<Integer> lis = new ArrayList<>();
                lis.add(intervals[i-1][0]);
                lis.add(intervals[i-1][1]);
                list.add(lis);
            }
        }
        List<Integer> end = new ArrayList<>();
        end.add(intervals[i-1][0]);
        end.add(intervals[i-1][1]);
        list.add(end);
        int[][] merge = new int[list.size()][2];
        for(int j = 0; j < list.size(); j++){
            merge[j][0] = list.get(j).get(0);
            merge[j][1] = list.get(j).get(1);
        }
        return merge;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        leetcode56 leetcode56 = new leetcode56();
        int[][] merge = leetcode56.merge(intervals);
        for(int i = 0; i < merge.length; i++){
            System.out.println(merge[i][0] + " " + merge[i][1]);
        }
    }

}