合并区间

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

示例 1:

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

示例 2:

1
2
3
4
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

提示：

  • intervals[i][0] <= intervals[i][1]

代码：

38%50%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals,  (a, b) -> a[0] - b[0]);
        List<int[]> ls = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            //取出当前点
            int L = intervals[i][0], R = intervals[i][1];
            //要是不符合，就把当前点放到队列中
            if (ls.size() == 0 || ls.get(ls.size() - 1)[1] < L) {
                ls.add(new int[]{L, R});
            } else {
                //要是符合范围的，就把队列最后一个元素修改成最大范围值
                ls.get(ls.size() - 1)[1] = Math.max(ls.get(ls.size() - 1)[1], R);
            }
        }
        return ls.toArray(new int[ls.size()][]);
    }
}