做买家秀的网站,站酷网如何接单,做网站的题目,做毕业设计网站的步骤【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主#xff0c;题解使用C语言。#xff08;若有使用其他语言的同学也可了解题解思路#xff0c;本质上语法内容一致题解使用C语言。若有使用其他语言的同学也可了解题解思路本质上语法内容一致 【题目描述】
给你一个 无重叠的 按照区间起始端点排序的区间列表 intervals其中 intervals[i] [starti, endi] 表示第 i 个区间的开始和结束并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval使得 intervals 依然按照 starti 升序排列且区间之间不重叠如果有必要的话可以合并区间。
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
【示例一】
输入intervals [[1,3],[6,9]], newInterval [2,5]
输出[[1,5],[6,9]]
【示例二】
输入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]重叠。
【提示及数据范围】
0 intervals.length 10的4次方intervals[i].length 20 starti endi 10的5次方intervals 根据 starti 按 升序 排列newInterval.length 20 start end 10的5次方
【代码】
class Solution {
public:vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) {int left newInterval[0];int right newInterval[1];bool placed false;vectorvectorint 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;}
};
