题目描述

以数组 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].

题目分析

把区间按起点从小到大排序。
从第一个开始尝试合并，如果后面的区间和当前区间有重叠，就合并。
否则就将当前区间入库，把下一个区间当作起点继续尝试合并。
主要耗时在排序，因此时间复杂度 O(n * log n)

Java

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return Integer.compare(o1[0], o2[0]);
        }
    });

    int count = 0;
    int[] cur = intervals[0];
    for (int[] array : intervals) {
        if (array[0] > cur[1]) {
            intervals[count++] = cur;
            cur = array;
        } else if (array[1] > cur[1]) {
            cur[1] = array[1];
        }
    }
    intervals[count++] = cur;
    return Arrays.copyOf(intervals, count);
}

Kotlin

fun merge(intervals: Array<IntArray>): Array<IntArray> {
    val ans = mutableListOf<IntArray>()
    Arrays.sort(intervals, object : Comparator<IntArray> {
        override fun compare(o1: IntArray, o2: IntArray): Int {
            return o1[0].compareTo(o2[0])
        }
    })

    var cur = intervals[0]
    for (array in intervals) {
        if (array[0] > cur[1]) {
            // 出现间隔，前面的数据入库
            ans.add(cur)
            cur = array
        } else if (array[1] >= cur[1]) {
            // 需要合并
            cur[1] = array[1]
        }
    }
    ans.add(cur)
    return ans.toTypedArray()
}