C++에서 간격 제거

분리된 간격의 정렬된 목록이 있다고 가정하고 각 간격 간격[i] =[a, b]은 a <=x

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• manipulate2()라는 메서드를 정의하면 행렬 a와 배열 y가 필요합니다.
• x :=행렬의 마지막 행, 다음에서 마지막 행 삭제
• z :=x
• x[0] :=y[1], z[1] :=y[0]
• z[0] − z[1]이면 z를 a에 삽입
• x[0] − x[1]이면 x를 a에 삽입
• 메인 메소드는 행렬 입력과 배열 t를 사용합니다.
• 행렬 ans 및 n :=행렬의 행 수 정의
• 0 ~ n –
  범위의 i에 대해
  • ins에 [i]를 삽입
  • a :=마지막 행, b :=t
  • a[0]> b[0]이면 와 b를 교환합니다.
  • 만약 a와 b가 교차한다면, 조작2(ans, t)를 호출
• 반환

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
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:
   bool isIntersect(vector <int> a, vector <int> b){
      return max(a[0], a[1]) >= min(b[0], b[1]);
   }
   void manipulate2(vector < vector <int> > &a, vector <int> y){
      vector <int> x = a.back();
      a.pop_back();
      vector <int> z = x;
      x[0] = y[1];
      z[1] = y[0];
      if(z[0] < z[1])a.push_back(z);
      if(x[0] < x[1])a.push_back(x);
   }
   vector<vector<int>> removeInterval(vector<vector<int>>& in, vector<int>& t) {
      vector < vector <int> > ans;
      int n = in.size();
      for(int i = 0; i < n; i++){
         ans.push_back(in[i]);
         vector <int> a;
         vector <int> b;
         a = ans.back();
         b = t;
         if(a[0]>b[0])swap(a, b);
         if(isIntersect(a, b)){
            manipulate2(ans, t);
         }
      }
      return ans;
   }
};
main(){
   vector<int> v2 = {1,6};
   vector<vector<int>> v1 = {{0,2},{3,4},{5,7}};
   Solution ob;
   print_vector(ob.removeInterval(v1, v2));
}

입력

[[0,2],[3,4],[5,7]]
[1,6]

출력

[[0, 1, ],[6, 7, ],]