Phong bì búp bê Nga trong C ++

Giả sử chúng ta có một số phong bì, các phong bì này có giá trị chiều cao và chiều rộng là các cặp. Chúng ta có thể đặt một phong bì này vào một phong bì khác nếu cả chiều cao và chiều rộng của phong bì thứ hai đều nhỏ hơn chiều cao và chiều rộng của phong bì thứ nhất. Vì vậy, số lượng phong bì tối đa mà chúng ta có thể đặt bên trong khác sẽ là bao nhiêu. Vì vậy, nếu các đầu vào như [[5,5], [6,4], [6,8], [2,3]], thì đầu ra sẽ là 3, vì bao nhỏ nhất là [2,3], sau đó [5,5], sau đó [6,8].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sắp xếp mảng v dựa trên chiều cao, khi các chiều cao giống nhau, hãy so sánh với chiều rộng
• nếu kích thước của v bằng 0, thì -
  • trả về 0
• Xác định ret mảng
• để khởi tạo i:=0, khi tôi
• Xác định một mảng temp =v [i]
• x:=temp [1]
• low:=0, high:=size of ret, curr:=0
• while low <=high, do -
  • giữa:=low + (cao - thấp) / 2
  • nếu ret [mid]
  • curr:=mid + 1
  • thấp:=giữa + 1
• Mặt khác
  • cao:=giữa - 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

3