C++의 러시아 인형 봉투

일부 봉투가 있다고 가정하고 이러한 봉투에는 높이와 너비 값이 쌍으로 있습니다. 두 번째 봉투의 높이와 너비가 모두 첫 번째 봉투의 높이와 너비보다 작으면 한 봉투를 다른 봉투에 넣을 수 있습니다. 그래서, 우리가 다른 봉투 안에 넣을 수 있는 최대 봉투 수는 몇 개입니까? 따라서 입력이 [[5,5], [6,4], [6,8], [2,3]]과 같으면 가장 작은 봉투가 [2,3]이므로 출력은 3이 됩니다. 다음 [5,5], 다음 [6,8].

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

• 높이를 기준으로 배열 v 정렬, 높이가 같을 때 너비와 비교
• v의 크기가 0과 같으면 -
  • 0을 반환
• ret 배열 정의
• 초기화 i의 경우:=0, i
• 배열 temp =v[i] 정의
• x :=온도[1]
• 낮음 :=0, 높음 :=ret 크기, curr :=0
• 낮은 <=높은 동안 −
  • 중간 :=낮음 + (높음 - 낮음) / 2
  • ret[mid]
  • 커 :=중간 + 1
  • 낮음 :=중간 + 1
• 그렇지 않으면
  • 높음 :=중간 - 1

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

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   static bool cmp(vector <int> a, vector <int> b){
      if(a[0] == b[0])return a[1] > b[1];
      return a[0] < b[0];
   }
   int maxEnvelopes(vector<vector<int>>& v) {
      sort(v.begin(), v.end(), cmp);
      if(v.size() == 0)return 0;
      vector <int> ret;
      for(int i = 0; i < v.size(); i++){
         vector <int> temp = v[i];
         int x = temp[1];
         int low = 0;
         int high = ret.size() -1;
         int curr = 0;
         while(low <= high){
            int mid = low + (high - low) / 2;
            if(ret[mid]<temp[1]){
               curr = mid + 1;
               low = mid + 1;
            }else{
               high = mid - 1;
            }
         }
         if(curr < 0) continue;
         if(curr >= (int)ret.size()){
            ret.push_back(temp[1]);;
         }else{
            ret[curr] = temp[1];
         }
      }
      return ret.size();
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{5,5}, {6,4}, {6,8}, {2,3}};
   cout << (ob.maxEnvelopes(v));
}

입력

{{5,5}, {6,4}, {6,8}, {2,3}}

출력

3