在C ++中插入间隔

假设我们有一组不重叠的间隔；我们必须在间隔中插入一个新间隔。如有必要，我们可以合并。因此，如果输入类似于-[[1,4]，[6,9]]，而新间隔为[2,5]，则输出将为[[1,5]，[6,9]]。

为了解决这个问题，我们将遵循以下步骤-

• 在上一个间隔列表的末尾插入新间隔

• 根据间隔的初始时间对间隔列表进行排序，n：=间隔数

• 创建一个称为ans的数组，将第一个间隔插入ans

• 指数：= 1

• 当索引<n时，

• 设置ans [last，0]：= ans [last，0]，interval [index，0]的最小值

• 设置ans [last，1]：= ans [last，1]的最小值，interval [index，1]

• last：= ans的大小– 1

• 如果ans [last，0]和ans [last，1]的最大值<interval [index，0]，intervals [index，1]的最小值，则将interval [index]插入ans

• 除此以外

• 指数增加1

• 返回ans

示例

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   static bool cmp(vector <int> a, vector <int> b){
      return a[0]<b[0];
   }
   vector<vector <int>>insert(vector<vector <int> >& intervals, vector <int>& newInterval) {
      intervals.push_back(newInterval);
      sort(intervals.begin(),intervals.end(),cmp);
      int n = intervals.size();
      vector <vector <int>> ans;
      ans.push_back(intervals[0]);
      int index = 1;
      bool done = false;
      while(index<n){
         int last = ans.size()-1;
         if(max(ans[last][0],ans[last][1])<min(intervals[index][0],intervals[i ndex][1])){
            ans.push_back(intervals[index]);
         } else {
            ans[last][0] = min(ans[last][0],intervals[index][0]);
            ans[last][1] = max(ans[last][1],intervals[index][1]);
         }
         index++;
      }
      return ans;
   }
};
main(){
   vector<vector<int>> v = {{1,4},{6,9}};
   vector<int> v1 = {2,5};
   Solution ob;
   print_vector(ob.insert(v, v1));
}

输入项

[[1,4],[6,9]]
[2,5]

输出结果

[[1, 5, ],[6, 9, ],]