- 难度：
中等 - 本题涉及算法：
贪心 - 思路：
贪心 - 类似题型：
题目 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] 可被视为重叠区间。
方法一 贪心
解题思路
- 当前下标和结果集中 最后一个数组的末尾元素进行比较(在错误的思维中，总会出现当前数组和下一个数组的比较)
- 按照左端点升序排序，然后遍历。
- 如果当前遍历到的区间的左端点 > 结果集中最后一个区间的右端点，说明它们没有交集，此时把区间添加到结果集；
- 如果当前遍历到的区间的左端点 <= 结果集中最后一个区间的右端点，说明它们有交集，此时产生合并操作，即：对结果集中最后一个区间的右端点更新（取两个区间的最大值）。
python
class Solution(object):
def merge(self, intervals):
if not intervals:
return []
intervals.sort() # 按照起点排序
ans = [intervals[0]] #
for i in range(1,len(intervals)):
if intervals[i][0]<=ans[-1][1]:
if intervals[i][1]<=ans[-1][1]:
ans[-1][1] = ans[-1][1]
else:
ans[-1][1] = intervals[i][1]
else:
ans.append(intervals[i])
return ans
优化版
class Solution(object):
def merge(self, intervals):
if not intervals:
return []
intervals.sort() # 按照起点排序
ans = [intervals[0]] #
for i in range(1,len(intervals)):
if intervals[i][0]<=ans[-1][1]:
ans[-1][1] = max(ans[-1][1],intervals[i][1])
# if intervals[i][1]<=ans[-1][1]:
# ans[-1][1] = ans[-1][1]
# else:
# ans[-1][1] = intervals[i][1]
else:
ans.append(intervals[i])
return ans
java
int len = intervals.length;
if (len < 2) {
return intervals;
}
// 按照起点排序
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
List<int[]> res = new ArrayList();
res.add(intervals[0]);
for (int i = 1; i < len; i++) {
int[] curInterval = intervals[i];
// 每次新遍历到的列表与当前结果集中的最后一个区间的末尾端点进行比较
int[] peek = res.get(res.size() - 1);
if (curInterval[0] > peek[1]) {
res.add(curInterval);
} else {
// 注意，这里应该取最大
peek[1] = Math.max(curInterval[1], peek[1]);
}
}
return res.toArray(new int[res.size()][]);
方法二
解题思路
2 个区间的关系有以下 6 种，但是其实可以变成上面 3 种情况（只需要假设 第一个区间的起始位置 ≤ 第二个区间的起始位置，如果不满足这个假设，交换这两个区间）。这 3 种情况的合并的逻辑都很好写。
class Solution {
public int[][] merge(int[][] intervals) {
// 先按照区间起始位置排序
Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
// 遍历区间
int[][] res = new int[intervals.length][2];
int idx = -1;
for (int[] interval: intervals) {
// 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
// 则不合并，直接将当前区间加入结果数组。
if (idx == -1 || interval[0] > res[idx][1]) {
res[++idx] = interval;
} else {
// 反之将当前区间合并至结果数组的最后区间
res[idx][1] = Math.max(res[idx][1], interval[1]);
}
}
return Arrays.copyOf(res, idx + 1);
}
}
知识点
- java 使用Arrays对二维数组个性化排序
- Arrays.sort(people, Comparator.comparingInt(o -> o[0])); 按照index0 排序
- Arrays.sort(people, Comparator.comparingInt(o -> o[1])); 按照index1 排序
- Arrays.copyOf() 用法
PREVIOUS69. x 的平方根
NEXT55. 跳跃游戏