文章目录
56. 合并区间：样例 1：样例 2：提示：
分析：题解：rust：go：c++：python：java：
56. 合并区间：
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
样例 1：
输入：
intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：
[[1,6],[8,10],[15,18]]
解释：
区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
样例 2：
输入：
intervals = [[1,4],[4,5]]
输出：
[[1,5]]
解释：
区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
分析：
面对这道算法题目，二当家的再次陷入了沉思。如果没想到排序是比较麻烦的，而下定决定使用排序也不是那么容易，因为排序本身的时间复杂度也不低，但是对于这个情况来说，还是很值得的。区间有两个值，应该按照开始值排序，而不是末尾值，当然逆向处理也是可以的，但是违背常理。根据区间开始值排序，前一个区间的末尾和下一个区间的开始值会出现几种情况：
前一个区间和后一个区间没有交集，那么当前区间就处理完毕，直接开始处理下一个区间。前一个区间和后一个区间有部分重叠，那么就将两个区间合并，然后接着处理下一个区间。前一个区间完整包含了后一个区间，那么直接抛弃后一个区间，然后继续处理下一个区间。 后两种情况可以统一认为是有重叠，只需要统一处理为更新当前处理区间的末尾值即可。
题解：
rust：
impl Solution {
pub fn merge(mut intervals: Vec
intervals.sort_unstable();
let mut ans: Vec
let (mut l, mut r) = (intervals[0][0], intervals[0][1]);
intervals.iter().skip(1).for_each(|cur| {
if r < cur[0] {
// 没重合
ans.push(vec![l, r]);
l = cur[0];
r = cur[1];
} else {
// 重合
r = r.max(cur[1]);
}
});
ans.push(vec![l, r]);
return ans;
}
}
go：
func merge(intervals [][]int) [][]int {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
var ans [][]int
last := intervals[0]
for i := 1; i < len(intervals); i++ {
cur := intervals[i]
if last[1] < cur[0] {
// 没有重合
ans = append(ans, last)
last = cur
} else {
// 有重合
if cur[1] > last[1] {
last[1] = cur[1]
}
}
}
ans = append(ans, last)
return ans
}
c++：
class Solution {
public:
vector
sort(intervals.begin(), intervals.end());
vector
for (int i = 0; i < intervals.size(); ++i) {
const int l = intervals[i][0], r = intervals[i][1];
if (ans.empty() || ans.back()[1] < l) {
ans.push_back({l, r});
} else {
ans.back()[1] = max(ans.back()[1], r);
}
}
return ans;
}
};
python：
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
ans = []
for interval in intervals:
if not ans or ans[-1][1] < interval[0]:
# 不重合
ans.append(interval)
else:
# 重合
ans[-1][1] = max(ans[-1][1], interval[1])
return ans
java：
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
final List
int[] last = intervals[0];
for (int i = 1; i < intervals.length; ++i) {
final int[] cur = intervals[i];
if (last[1] < cur[0]) {
// 没重合
ans.add(last);
last = cur;
} else {
// 重合
last[1] = Math.max(last[1], cur[1]);
}
}
ans.add(last);
return ans.toArray(new int[ans.size()][]);
}
}
非常感谢你阅读本文~ 欢迎【点赞】【收藏】【评论】~ 放弃不难，但坚持一定很酷~ 希望我们大家都能每天进步一点点~ 本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~
精彩内容
发表评论