【Leetcode】56.合并区间

56 合并区间

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

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

思路：
先将数组intervals按照第一个元素的大小从小到大排序。之后遍历数组intervas中的每一个区间。

  • 如果该区间的左端点大于res中最后一个区间的右端点，则不重合、不需要合并，直接将这个区间加入到res的末尾。
  • 否则，需要合并，即用该区间的右端点更新res中最后一个区间的右端点，取二者的最大值。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int[][] merge(int[][] intervals) {
    if(intervals == null || intervals.length == 0)
        return new int[0][0];
    if(intervals.length == 1)
        return intervals;
    //初始化结果数组，大小为intervals的长度
    int[][] res = new int[intervals.length][2];
    //将数组intervals按照第一个元素的大小进行升序排序
    Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
    //先将第一个区间加入结果集
    int index = 0;
    res[index++] = intervals[0];
    //遍历数组中的每一个区间
    for(int i = 1; i < intervals.length; i++){
        if(intervals[i][0] > res[index - 1][1]){
            res[index++] = intervals[i];
        }
        else{
            res[index - 1][1] = Math.max(res[index - 1][1], intervals[i][1]);
        }
    }
    //由于res初始化时长度为intervals.length
    //因此最后只需要返回它的前index+1个元素的拷贝
    return Arrays.copyOf(res, index);
}