C++의 포함된 간격

각 간격에 두 개의 값[start, end]이 있는 간격의 2차원 목록이 있다고 가정합니다. 다른 간격을 포함하는 간격이 있는지 여부를 찾아야 합니다.

따라서 입력이 [[2,4],[5,11],[5,9],[10,10]]과 같으면 출력은 [5,11]에 [5, 9].

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

배열 v
정렬
하나의 2D 배열 ret 정의
각 간격에 대해 v −
- ret가 비어 있으면 -
  - ret의 끝에 삽입
- 그렇지 않으면 ret>=it[0]의 마지막 요소인 경우 -
  - true를 반환
- 그렇지 않으면
  - ret의 끝에 삽입
거짓을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool static cmp(vector<int> &a, vector<int> &b) {
      return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
   }
   bool solve(vector<vector<int>> &v) {
      sort(v.begin(), v.end(), cmp);
      vector<vector<int>> ret;
      for (auto &it : v) {
         if (ret.empty())
         ret.push_back(it);
         else if (ret.back()[0] >= it[0])
         return true;
         else
         ret.push_back(it);
      }
      return false;
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {{2,4},{5,11},{5,9},{10,10}};
   cout << (ob.solve(v));
}

입력

{{2,4},{5,11},{5,9},{10,10}}