题目
给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 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]]
解题
方法一：
比如[1,2]区间的 2<4，那么直接加入到res中
比如[3,5]与新区间有交集，那么直接新区间合并为[3,8]，…以此类推
比如[12,14] 的 14比新插入区间的末尾10大，因此直接加入到res中
写法一：
class Solution { public: vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { vector<vector<int>> res; int i=0,n=intervals.size(); while(i<n&&intervals[i][1]<newInterval[0]){ res.push_back(intervals[i]); i++; } while(i<n&&intervals[i][0]<=newInterval[1]){ newInterval[0]=min(intervals[i][0],newInterval[0]); newInterval[1]=max(intervals[i][1],newInterval[1]); i++; } res.push_back(newInterval); while(i<n){ res.push_back(intervals[i]); i++; } return res; } };
写法二：
class Solution { public: vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { vector<vector<int>> res; bool flag=false; for(int i=0;i<intervals.size();i++){ if(intervals[i][1]<newInterval[0]){ res.push_back(intervals[i]); }else if(intervals[i][0]>newInterval[1]){ if(flag==false){ res.push_back(newInterval); flag=true; } res.push_back(intervals[i]); }else { newInterval[0]=min(newInterval[0],intervals[i][0]); newInterval[1]=max(newInterval[1],intervals[i][1]); } } if(flag==false) res.push_back(newInterval); return res; } };
