141、【贪心算法】leetcode ——56. 合并区间(区间重叠解法+双指针解法)(C++版本)
2023-09-11 14:20:01 时间
题目描述
原题链接:56. 合并区间
解题思路
局部最优解: 按区间左边界从小到大排列,合并时候按最大右边界合并。
全局最优解: 合并所有有重叠的区间。
(1)合并重叠区间,对最后一个单独处理
先按左边界从小打到排序,每次前后两个区间对比,无重叠则将前面的区间加入结果集,有重叠则将两个区间合并。对最后一个区间大度处理。
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size() == 1) return intervals;
sort(intervals.begin(), intervals.end(), cmp);
vector<vector<int>> res;
int n = intervals.size();
for(int i = 1; i < n; i++) {
if(intervals[i - 1][1] < intervals[i][0]) { // 无重叠,将前面的加入
res.push_back(intervals[i - 1]);
} else { // 有重叠,将前面的合并
intervals[i][0] = intervals[i - 1][0];
intervals[i][1] = max(intervals[i][1], intervals[i - 1][1]);
}
}
// 对最后一个区间处理
if(intervals[n - 2][1] >= intervals[n - 1][0]) { // 有重叠,则合并
intervals[n - 1][0] = intervals[n - 2][0];
intervals[n - 1][1] = max(intervals[n - 1][1] ,intervals[n - 2][1]);
}
res.push_back(intervals[n - 1]);
return res;
}
};
(2)双指针方法
设置一个左边界和右边界指针,从第一个开始和后一个对比,若重叠则合并,若不重叠则直接加入。
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size() == 1) return intervals;
sort(intervals.begin(), intervals.end(), cmp);
vector<vector<int>> res;
int n = intervals.size();
for(int i = 0; i < n; i++) { // 注这个外面的for对比到n,里面的对比到n - 1,可以让最后一个一块都合并
int l = intervals[i][0], r = intervals[i][1]; // 获取第一个的左边界和右边界
while(i < n - 1 && r >= intervals[i + 1][0]) { // 第一个的右边界和第二个的左边界进行对比
r = max(r, intervals[i + 1][1]); // 若有重叠,则合并
i++;
}
res.push_back({l, r});
}
return res;
}
};
参考文章:【合并区间】排序 + 双指针、56. 合并区间
相关文章
- LeetCode-899. 有序队列【数学,c++】
- C++数据结构--异常类与顶层父类的实现
- 汉明距离(C++)
- C++ Qt开发——写日志文件
- 在C++中,你真的会用new吗?
- 【华为OD机试 2023最新 】 星际篮球争霸赛(C++)
- 【华为OD机试 2023】模拟商场优惠打折(C++ Java JavaScript Python)
- How to get the window id of a window using c++ program in ubuntu?
- [LeetCode] 032. Longest Valid Parentheses (Hard) (C++)
- Eclipse配置C/C++开发环境
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- PCL 点云投影到直线(C++详细过程版)