56. 合并区间

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

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

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

二维数组排序：

// 先升序排序
Arrays.sort(intervals, (i1,i2) -> i1[0]-i2[0]);

方法1：（227ms）

    public static int[][] merge(int[][] intervals) {
        sort(intervals);
        int[][] result = new int[intervals.length][2];
        int index = 0;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int[] interval : intervals) {
            if (queue.size() == 0){
                queue.addLast(interval[0]);
                queue.addLast(interval[1]);
            } else {
                if (interval[0] <= queue.getLast()){
                    if (interval[1] > queue.getLast()){
                        queue.removeLast();
                        queue.addLast(interval[1]);
                    }
                }else {
                    result[index][0] = queue.removeFirst();
                    result[index][1] = queue.removeLast();
                    index++;
                    queue.addLast(interval[0]);
                    queue.addLast(interval[1]);
                }
            }
        }
        result[index][0] = queue.getFirst();
        result[index][1] = queue.getLast();
        result = Arrays.copyOf(result, index + 1);
        return result;
    }
    public static int[][] sort(int[][] srcArrays){
        for (int i = 0; i < srcArrays.length - 1; i++) {
            for (int j = i + 1; j < srcArrays.length; j++) {
                if (srcArrays[i][0] > srcArrays[j][0]){
                    int temp[] = srcArrays[i];
                    srcArrays[i] = srcArrays[j];
                    srcArrays[j] = temp;
                }
            }
        }
        return srcArrays;
    }

方法2：（0ms）

    static int[][] merge(int[][] intervals) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int[] x : intervals) {
            min = Math.min(min, x[0]);
            max = Math.max(max, x[0]);
        }
        int[] range = new int[max - min + 1];

        for (int i = 0; i < intervals.length; i++) {
            // 记录了从某个start出发，最大结束区间是在哪里。即： range[start] = max(range[end])
            range[intervals[i][0] - min] = Math.max(intervals[i][1] - min, range[intervals[i][0] - min]);
        }
        int start = 0;
        int end = 0;
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < range.length; i++) {
            if (range[i] == 0) {
                // 没有从这个start出发的。
                continue;
            }
            // 如果有，就计算这个点能到多远
            if (i <= end) {
                // 这个start在end以内，说明可以连接起来
                end = Math.max(range[i], end);
            } else {
                // 这个satrt超出了end的范围，说明找到了一个区间。
                res.add(new int[] { start + min, end + min });
                start = i;
                end = range[i];
            }
        }
        res.add(new int[] { start + min, end + min });
        return res.toArray(new int[res.size()][]);
    }

方法3：（2ms）

    public int[][] merge(int[][] intervals) {
        quickSort(intervals,0,intervals.length-1);
        List<int[]> ans = new ArrayList();
        ans.add(intervals[0]);
        for(int[] interval :  intervals){
            int[] ansInterval = ans.get(ans.size()-1);
            if(ansInterval[1] < interval[0]){
                ans.add(interval);
            }else{
                ansInterval[1] = Math.max(ansInterval[1],interval[1]);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }

方法4：（8ms）

public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历区间
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval: intervals) {
            // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
            // 则不合并，直接将当前区间加入结果数组。
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                // 反之将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, idx + 1);
    }

作者：Sweetiee 🍬
链接：https://leetcode.cn/problems/merge-intervals/solutions/204805/chi-jing-ran-yi-yan-miao-dong-by-sweetiee/

方法5（9ms）

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> ans = new ArrayList<>();
        for (int i = 0; i < intervals.length; ++i) {
            if (ans.size() == 0 || intervals[i][0] > ans.get(ans.size() - 1)[1]) ans.add(intervals[i]);
            else ans.get(ans.size() - 1)[1] = Math.max(intervals[i][1], ans.get(ans.size() - 1)[1]);
        }
        return ans.toArray(new int[ans.size()][2]);
    }