题目描述

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

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

https://leetcode-cn.com/problems/merge-intervals/

解法1

为了便于描述,我们将区间记为interval,左边界记为interval.start, 右边界记为interval.end。我们将区间列表按照start排序,如果区间i与区间j相交,那么有interval[j].start <= interval[i].end(i<j)。

图1 区间合并case1
图2 区间合并case2

图1与图2绘制了区间合并的两种case,我们已经将区间列表按照start排序好了。图1中区间{1, 3}与{2, 6}相交,第二个区间的end=6大于第一个区间的end = 3,合并后区间为{1, 6}。图2中区间{1, 4}与区间{2, 3}相交,第二个区间的end=3小于第一个区间的end=4,合并后区间为{1, 4}。通过这两个case能够启发我们,如果区间i与区间j合并,那么合并后区间的end应该取二者较大的

现在我们描述下算法流程,首先将第一个区间加入结果集,结果集是存放合并后区间的容器。然后遍历余下的每个区间(记为currInterval),我们取结果集最后一个区间(记为lastInterval),将currInterval与lastInterval对比,如果存在交集,将currInterval与lastInterval合并,合并后的区间写回lastInterval;如果不存在交集,将currInterval追加到结果集。

目前,leetcode-cn上这道题目的函数签名为“public List merge(List intervals) ”,但是实际上函数签名已经改为“public int[][] merge(int[][] intervals)”。intervals[i][0]代表第i个区间的左边界,intervals[i][1]代表第i个区间的右边界。下面是全部代码,因为涉及到排序,所以时间复杂度O(nlogn),空间复杂度O(n)。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

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

        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        List<int[]> merged = new ArrayList<>();

        merged.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] lastInterval = merged.get(merged.size() - 1);
            int[] currInterval = intervals[i];

            if (currInterval[0] <= lastInterval[1])
                lastInterval[1] = Math.max(lastInterval[1], currInterval[1]);
            else
                merged.add(currInterval);
        }

        return merged.toArray(new int[merged.size()][]);
    }
}
pwrliang Algorithms, Array, Interval ,

Leave a Reply

Your email address will not be published. Required fields are marked *