leetcode56 区间合并
合并 区间
2023-09-27 14:27:45 时间
题目:给出一个区间集合,求合并所有重叠后的区间。
分析:区间处理先上套路,按左端点作第一维,右端点作第二维进行排序。依次考察每个区间,假设前面所有区间合并后是[left, right],若当前区间的左端点小于等于right,right=max(right, 当前区间的右端点);否则说明有空格,将[left, right]加入答案,新区间作为[left, right]。
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { int n = intervals.size(); if(n == 0) return {}; vector<vector<int>>ans; vector<pair<int, int>>myinter; for(int i = 0;i < n;i++) myinter.push_back(make_pair(intervals[i][0], intervals[i][1])); sort(myinter.begin(), myinter.end()); int left = myinter[0].first, right = myinter[0].second; for(int i = 1;i < n;i++) { if(myinter[i].first <= right) right = max(right, myinter[i].second); else { ans.push_back(vector<int>{left, right}); left = myinter[i].first; right = myinter[i].second; } } ans.push_back(vector<int>{left, right}); return ans; } };
推荐用pair实现,因为pair会自动将first作第一关键字,second作第二关键字排序,这样就不用自己写个cmp函数。
相关文章
- HDU 5358(2015多校联合训练赛第六场1006) First One (区间合并+常数优化)
- Python合并多个Excel数据
- Wireshark 文件分割和合并
- 【BZOJ3995】[SDOI2015]道路修建 线段树区间合并
- Oracle数据库:oracle函数嵌套,nvl函数,nvl2函数,nullif函数,coalesce合并函数
- Github | 制作您的第一个开源合并请求
- win11设置任务栏不合并的方法教程
- requirejs 合并方案
- IDEA合并分支(从开发分支到测试分支)
- el-table合并表格
- Python代码大全之如何合并append两个字典
- SVN合并时报错:Merge tracking not allowed with missing subtrees; try restoring these items
- git项目实现合并一个分支的代码到另一个分支
- matlab simulnk笔记07——模块(接地模块group、终止模块terminal、信号合并mux与分解模块demux)
- 【bzoj2325】[ZJOI2011]道馆之战 树链剖分+线段树区间合并
- 【bzoj3638】Cf172 k-Maximum Subsequence Sum 模拟费用流+线段树区间合并
- 【bzoj3747】[POI2015]Kinoman 线段树区间合并
- 【bzoj3091】城市旅行 LCT区间合并