56. 合并区间

力扣题目链接(opens new window)

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

示例 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] 可被视为重叠区间。
  • 注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

#思路

大家应该都感觉到了，此题一定要排序，那么按照左边界排序，还是右边界排序呢？

都可以！

那么我按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。

局部最优可以推出全局最优，找不出反例，试试贪心。

那有同学问了，本来不就应该合并最大右边界么，这和贪心有啥关系？

有时候贪心就是常识！哈哈

按照左边界从小到大排序之后，如果 intervals[i][0] < intervals[i - 1][1] 即intervals[i]左边界 < intervals[i - 1]右边界，则一定有重复，因为intervals[i]的左边界一定是大于等于intervals[i - 1]的左边界。

即：intervals[i]的左边界在intervals[i - 1]左边界和右边界的范围内，那么一定有重复！

这么说有点抽象，看图：（注意图中区间都是按照左边界排序之后了）

56.合并区间

知道如何判断重复之后，剩下的就是合并了，如何去模拟合并区间呢？

其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。

Java代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int[][] merge(int[][] intervals) {
    int left = intervals[0][0];
    int right = intervals[0][1];
    Arrays.sort(intervals,(a,b) -> {
        return a[0] - b[0];
    })
    List<int[]> res= new ArrayList<>();
    for(int i = 1;i < intervals.length;i++) {
        // 不能合并时
        if(intervals[i][0] < right) {
            res.add(new int[] {left,right});
            left = intervals[i][0];
            right = intervals[i][1];
        } else {
            right = Math.max(right,intervals[i][1]);
        }
    }
    res.add(new int[] {left,right});
    return res.toArray(new int[res.size()][])
}