深圳网站制作联系电话/百度系优化

题目：

题解：

思路1：直接将新区间 b 添加到区间 a 中，然后调用56. 合并区间的代码即可。这样的时间复杂度是$O(n\ast logn)$的，可以使用思路2中线性插入。

---

思路2：线性查找插入区间点，进行插入。时间复杂度$O(n)$。

代码如下：

// 思路1代码
class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& q, vector<int>& p) {q.push_back(p);return merge(q);}// 区间贪心：排序之后进行区间贪心即可，若左端点不同，则按左端点由小到大排序；若左端点相同，则按右端点由小到大排序vector<vector<int>> merge(vector<vector<int>>& q) {sort(q.begin(),q.end());vector<vector<int>> res;for(auto it:q){// 初始区间为空或者维护区间的右端点小于当前区间的左端点，则表示找到了一个新的区间，添加这个新区间即可if(res.empty()||res.back()[1]<it[0]){res.push_back(it);}// 维护区间的右端点大于等于当前的区间的左端点，则可以进行区间合并了，更新维护区间右端点即可else{res.back()[1]=max(res.back()[1],it[1]);// 进行区间合并，更新新区间的右端点}}return res;}
};

// 思路2代码
class Solution {
public:// 这题直接画图的比较好理解，然后按照图的思路写代码就好了vector<vector<int>> insert(vector<vector<int>>& a, vector<int>& b) {int idx=0,n=a.size();vector<vector<int>> res;// 1、先跳过未覆盖的区间，即当前区间的右端点小于插入区间的左端点，表示未覆盖，则跳过while(idx<n&&a[idx][1]<b[0])res.push_back(a[idx++]);// 2、进行合并区间，当前区间的左端点小于等于插入区间的右端点，则进行区间合并；直到当前区间的左端点大于插入区间的右端点为止while(idx<n&&a[idx][0]<=b[1]){b[0]=min(b[0],a[idx][0]);b[1]=max(b[1],a[idx][1]);idx++;}// 添加合并之后的新区间res.push_back(b);// 3、继续添加合并区间之后的区间while(idx<n)res.push_back(a[idx++]);return res;}
};