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

题目描述

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

题目示例

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

解题思路

首先将数组按照左边界按照从小到大进行排序，目的是为了让两个重叠的区间更容易相邻在一块，然后我们定义收集结果的数组 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()][]);}
}