重庆祥云平台做网站,公众号的维护与运营,石家庄网推公司,门户类网站建设需要多少钱【每日一题】57. 插入区间 57. 插入区间题目描述解题思路 57. 插入区间
题目描述
给你一个 无重叠的 #xff0c;按照区间起始端点排序的区间列表。
在列表中插入一个新的区间#xff0c;你需要确保列表中的区间仍然有序且不重叠#xff08;如果有必要的话#xff0c;可… 【每日一题】57. 插入区间 57. 插入区间题目描述解题思路 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] 重叠。示例 3
输入intervals [], newInterval [5,7]
输出[[5,7]]示例 4
输入intervals [[1,5]], newInterval [2,3]
输出[[1,5]]示例 5
输入intervals [[1,5]], newInterval [2,7]
输出[[1,7]]提示
0 intervals.length 104 intervals[i].length 2 0 intervals[i][0] intervals[i][1] 105 intervals 根据 intervals[i][0] 按 升序 排列 newInterval.length 2 0 newInterval[0] newInterval[1] 105
解题思路
思路将新区间插入区间列表再按照56合并区间方法合并区间。
class Solution {
public:vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) {// 将新区间加入区间列表intervals.push_back(newInterval);// 区间按照左端点排序sort(intervals.begin(),intervals.end());// 合并区间咯int nintervals.size();// 结果区间vectorvectorint res;res.push_back(intervals[0]);for(int i1;in;i){if(intervals[i][0]res.back()[1])res.push_back(intervals[i]);elseres.back()[1]max(res.back()[1],intervals[i][1]);}return res;}
};优化原本区间列表已经有序那么可以利用该信息进行合并。将原有区间列表分为三部分第一部分是无重叠部分第二部分是有重叠部分第三部分是无重叠部分可以通过绘制线形图直观表示。
class Solution {
public:vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) {int nintervals.size();int i0;vectorvectorint res;// 第一部分无重叠区间while(innewInterval[0]intervals[i][1]){res.push_back(intervals[i]);i;}// 第二部分重叠区间 相当于将新区间与重叠区间不断合并然后更新合并区间// [[1,2],[3,5],[6,7],[8,10],[12,16]]while(innewInterval[1]intervals[i][0]){newInterval[0]min(newInterval[0],intervals[i][0]);newInterval[1]max(newInterval[1],intervals[i][1]);i;}// [[1,5]] [6,8] 即直接合并该newIntervalres.push_back(newInterval);// 第三部分无重叠区间while(in){res.push_back(intervals[i]);i;}return res;}
};总结注意因为原有区间列表有序故当第一部分无重叠区间处理完毕后后面即为第二部分有重叠区间此时满足newInterval[0]interval[i][1]那么有重叠区间的条件即为newInterval[1]interval[i][0]此时将新区间逐个与各个重叠区间进行合并同时更新新区间这样才能得到最后合并后的大区间。注意[[1,5]] [6,8] 即直接合并该newInterval。
