题目来源:https://leetcode.cn/problems/merge-intervals/description/
C++题解:根据左区间排序,更新每一段的右区间最大值,直到间断。文章来源:https://www.toymoban.com/news/detail-604040.html
class Solution {
public:
static bool cmp(vector<int> & a, vector<int> & b) {
return a[0] < b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), cmp);
int start = intervals[0][0], end = intervals[0][1];
vector<vector<int> >res;
vector<int> seg(2);
for(int i = 1; i < intervals.size(); i++) {
if(intervals[i][0] <= end) {
end = max(end, intervals[i][1]);
}
else{
// 添加当前区间,并且更新start和end,但是没有最后一个区间
seg[0] = start; start = intervals[i][0];
seg[1] = end; end = intervals[i][1];
res.push_back(seg);
}
}
// 添加最后一个区间
seg[0] = start;
seg[1] = end;
res.push_back(seg);
return res;
}
};
同思路,另一种写法(代码随想录)。文章来源地址https://www.toymoban.com/news/detail-604040.html
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
if (intervals.size() == 0) return result; // 区间集合为空直接返回
// 排序的参数使用了lambda表达式
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
// 第一个区间就可以放进结果集里,后面如果重叠,在result上直接合并
result.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
// 合并区间,只更新右边界就好,因为result.back()的左边界一定是最小值,因为我们按照左边界排序的
result.back()[1] = max(result.back()[1], intervals[i][1]);
} else {
result.push_back(intervals[i]); // 区间不重叠
}
}
return result;
}
};
到了这里,关于力扣 56. 合并区间的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!