मान लीजिए हमारे पास कुछ लिफाफे हैं, इन लिफाफों में जोड़े के रूप में ऊंचाई और चौड़ाई मान हैं। हम एक लिफाफे को दूसरे में रख सकते हैं यदि दूसरे लिफाफे की ऊंचाई और चौड़ाई दोनों पहले वाले की ऊंचाई और चौड़ाई से छोटी हों। तो, लिफाफों की अधिकतम संख्या क्या होगी जो हम दूसरे के अंदर रख सकते हैं। इसलिए, यदि इनपुट [[5,5], [6,4], [6,8], [2,3]] जैसे हैं, तो आउटपुट 3 होगा, क्योंकि सबसे छोटा लिफाफा [2,3] है, फिर [5,5], फिर [6,8]।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- ऊंचाई के आधार पर सरणी v को क्रमबद्ध करें, जब ऊंचाई समान हों, तो चौड़ाई के साथ तुलना करें
- यदि v का आकार 0 के समान है, तो −
- वापसी 0
- एक सरणी रिट परिभाषित करें
- इनिशियलाइज़ i :=0 के लिए, जब i
करें - एक सरणी परिभाषित करें अस्थायी =v[i]
- x:=अस्थायी[1]
- निम्न:=0, उच्च:=रेट का आकार, वक्र:=0
- कम <=उच्च होने पर, −
- . करें
- मध्य :=निम्न + (उच्च-निम्न)/2
- यदि रिट[मध्य] <अस्थायी[1], तो −
- करी :=मध्य + 1
- निम्न :=मध्य + 1
- अन्यथा
- उच्च :=मध्य - 1
- यदि वर्तमान <0, तो −
- निम्न भाग पर ध्यान न दें, अगले भाग पर जाएं
- यदि curr>=रिट का आकार, तो −
- रिट के अंत में
- अस्थायी डालें[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