【LeetCode面试150】——56合并区间
博客昵称：沈小农学编程
作者简介：一名在读硕士，定期更新相关算法面试题，欢迎关注小弟！
PS：哈喽！各位CSDN的uu们，我是你的小弟沈小农，希望我的文章能帮助到你。欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
题目难度：中等
默认优化目标：最小化时间复杂度。
Python默认为Python3。
目录
1 题目描述
2 题目分析
3 代码实现
3.1 排序
参考文献
1 题目描述
以数组 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 <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
2 题目分析
输入是区间数组intervals，输出是不重叠的区间数组merged。
这道题的难度在于找到合并的方法，即如何判断两个区间是重叠区间。
3 代码实现
3.1 排序
首先，我们按照区间的左端点进行升序排序。然后判断前一个区间的右端点是否小于后一个区间的左端点，是则为两个不重叠区间，直接添加进merged，否则进行合并。
正确性证明：反证法，设三元组(i,j,k)和数组中的三个区间a[i]，a[j]，a[k]满足i<j<k并且(a[i]，a[k])可以合并，但(a[i]，a[j])和(a[j]，a[k])不能合并。这说明：
联立不等式得
矛盾，所以假设不成立。因此，所有能够合并的区间都是必然连续的。
时间复杂度O(n logn)，空间复杂度O(log n)。
C++代码实现
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() == 0) {
return {};
}
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (int i = 0; i < intervals.size(); ++i) {
int L = intervals[i][0], R = intervals[i][1];
if (!merged.size() || merged.back()[1] < L) {
merged.push_back({L, R});
}
else {
merged.back()[1] = max(merged.back()[1], R);
}
}
return merged;
}
};Python代码实现
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1]<interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged参考文献
力扣面试经典150题
力扣官方题解