LeetCode 57. 插入区间
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5] 输出：[[1,5],[6,9]] 示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出：[[1,2],[3,10],[12,16]] 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/insert-interval 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。、
想到了 用 vector<vector<int>> ans;
然后遍历，但是没有想到 可以一直更新 left 和 right 然后在最后 插入一个就行
先判断插入的数区间 和内部区间有没有 交集，没有可以直接插入 ans
如果有交集 就更新交集的 left 和 right 在最后 把 left 和 right 插进去
C++ 代码 和官方题解一样
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int left = newInterval[0];
int right = newInterval[1];
bool placed = false;
vector<vector<int>> ans;
for (const auto& interval: intervals) {
if (interval[0] > right) {
// 在插入区间的右侧且无交集
if (!placed) {
ans.push_back({left, right});
placed = true;
}
ans.push_back(interval);
}
else if (interval[1] < left) {
// 在插入区间的左侧且无交集
ans.push_back(interval);
}
else {
// 与插入区间有交集，计算它们的并集
left = min(left, interval[0]);
right = max(right, interval[1]);
}
}
if (!placed) {
ans.push_back({left, right});
}
return ans;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-11-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录