ধরুন আমাদের কিছু খাম আছে, এই খামে জোড়া হিসাবে উচ্চতা এবং প্রস্থের মান রয়েছে। দ্বিতীয় খামের উচ্চতা এবং প্রস্থ উভয়ই প্রথমটির উচ্চতা এবং প্রস্থের চেয়ে ছোট হলে আমরা একটি খামকে অন্যটিতে রাখতে পারি। সুতরাং, খামের সর্বোচ্চ সংখ্যা কত হবে যা আমরা অন্যের ভিতরে রাখতে পারি। সুতরাং, যদি ইনপুটগুলি [[5,5], [6,4], [6,8], [2,3]] এর মত হয়, তাহলে আউটপুট হবে 3, যেমন ক্ষুদ্রতম খাম [2,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]
- curr :=mid + 1
- নিম্ন :=মধ্য + 1
- অন্যথায়
- উচ্চ :=মধ্য - 1
- নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
- ret এর শেষে temp[1] ঢোকান
- ret[curr] :=temp[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
