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