56. 合并区间

Scroll Down

合并区间

给出一个区间的集合,请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路

根据起点排序(比较器不会写),得到结果后确定一个区间的左界限,寻找比它小的右界限合并。当遇到左界限比它大,则说明后面的区间不能合并。

解答

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return new int[0][];

        // 比较器不会
        Arrays.sort(intervals, (first, second) -> first[0] - second[0]);
        int i = 0;
        List<int[]> result = new ArrayList<>();
        while (i < intervals.length) {
            int left = intervals[i][0];
            int right = intervals[i][1];

            while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
                i++;
                right = Math.max(right, intervals[i][1]);
            }

            result.add(new int[]{left, right});
            i++;
        }
        return result.toArray(new int[0][]);
    }
}