C++でのロシアの人形の封筒

いくつかのエンベロープがあると仮定します。これらのエンベロープには、高さと幅の値がペアで含まれています。 2番目のエンベロープの高さと幅の両方が最初のエンベロープの高さと幅よりも小さい場合は、1つのエンベロープを別のエンベロープに入れることができます。それで、私たちが他の中に入れることができるエンベロープの最大数は何でしょう。したがって、入力が[[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：=temp [1]
• 低：=0、高：=retのサイズ、curr：=0
• 低い<=高い間、-
  を実行します
  • 中：=低+（高-低）/ 2
  • ret [mid]
  • curr：=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