C++에서 포함된 간격 제거

구간 목록이 있다고 가정하고 목록의 다른 간격에 포함된 모든 간격을 제거해야 합니다. 여기서 간격 [a,b)는 c <=a 및 b <=d인 경우에만 간격 [c,d)에 포함됩니다. 따라서 그렇게 한 후에는 남은 간격의 수를 반환해야 합니다. 입력이 [[1,4],[3,6],[2,8]]과 같으면 출력은 2가 됩니다. 간격 [3,6]은 [1,4] 및 [2 ,8]이므로 출력은 2가 됩니다.

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

종료 시간을 기준으로 간격 목록 정렬
스택 st 정의
i의 경우 범위 0에서 a – 1의 크기
- 스택이 비어 있거나 a[i]이고 스택 상단 간격이 교차하는 경우,
  - st에 a[i] 삽입
- 그렇지 않으면
  - temp :=a[i]
  - st가 비어 있지 않고 temp와 스택 상단 간격이 교차하는 동안
    - 스택에서 팝
  - st에 온도 삽입
st.의 반환 크기

예(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool intersect(vector <int>& a, vector <int>& b){
      return (b[0] <= a[0] && b[1] >= a[1]) || (a[0] <= b[0] && a[1] >= b[1]);
   }
   static bool cmp(vector <int> a, vector <int> b){
      return a[1] < b[1];
   }
   void printVector(vector < vector <int> > a){
      for(int i = 0; i < a.size(); i++){
         cout << a[i][0] << " " << a[i][1] << endl;
      }
      cout << endl;
   }
   int removeCoveredIntervals(vector<vector<int>>& a) {
      sort(a.begin(), a.end(), cmp);
      stack < vector <int> > st;
      for(int i = 0; i < a.size(); i++){
         if(st.empty() || !intersect(a[i], st.top())){
            st.push(a[i]);
         }
         else{
            vector <int> temp = a[i];
            while(!st.empty() && intersect(temp, st.top())){
               st.pop();
            }
            st.push(temp);
         }
      }
      return st.size();
   }
};
main(){
   vector<vector<int>> v = {{1,4},{3,6},{2,8}};
   Solution ob;
   cout << (ob.removeCoveredIntervals(v));
}

입력

[[1,4],[3,6],[2,8]]