56. 合并区间 - 力扣（LeetCode）

问题描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

输入格式

intervals = [[1,3],[2,6],[8,10],[15,18]]
1

输出格式

[[1,6],[8,10],[15,18]]
1

解释

区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
1

解题思路
首先将每个数组元素按照左端点从小到大排序（可以用Java排序器实现），创建一个 merged 数组用来存放最终结果，然后依次遍历每一个数组元素取出左端点 L 和右端点 R，如果 merged 数组中无内容或当前遍历数组的左端点比 merged 最后一个元素右端点大（表示无重叠），则直接将该数组元素加入 merged 中，否则合并（即将 merged 最后一个元素的右端点变为其和当前数组元素选择最大值）

解题代码

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

        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });

        List<int[]> merged = new ArrayList<int[]>();
        for(int i = 0; i < intervals.length; i++) {
            int L = intervals[i][0];
            int R = intervals[i][1];
            if(merged.size()==0 || merged.get(merged.size()-1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size()-1)[1] = 
                Math.max(merged.get(merged.size()-1)[1], R);
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }
}
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