मान लीजिए हमारे पास N अलग-अलग आयतों की चौड़ाई और ऊंचाई है; हमें एक आयत को दूसरे में डालने के बाद बचे न्यूनतम आयतों की संख्या खोजनी है। यदि W1 और W2 आयतों R1 और R2 की चौड़ाई हैं। और H1 और H2 R1 और R2 की ऊंचाई हैं, तो यदि W1 < W2 और H1 < H2 तो आयत R1, आयत R2 के अंदर फिट हो जाता है। इस प्रकार, सबसे छोटा दूसरे सबसे छोटे में फिट हो सकता है, फिर वह अगले में फिट होता है, और इसी तरह।
उदाहरण के लिए, यदि इनपुट {{30, 45}, {15, 15}, {45, 30}, {60, 75}} है, तो आउटपुट 2 होगा क्योंकि संभावित तरीकों में से एक है दूसरे आयत को पहले में डालें और फिर उस आयत को चौथे में डालें। तीसरा और चौथा आयत बचे रहेंगे।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- n := बॉक्सेस का आकार
- बॉक्सेस ऐरे को उनके आकार के आधार पर सॉर्ट करें
- नेस्टेड नामक पेयर्स का एक ऐरे परिभाषित करें
- बॉक्सेस[n - 1] को नेस्टेड के अंत में डालें
- i := n - 2 से 0 तक घटते हुए लूप करें:
- राइट := नेस्टेड का आकार
- जब तक लेफ्ट <= राइट:
- मिड := (राइट + लेफ्ट) / 2
- यदि नेस्टेड[मिड] की ऊंचाई बॉक्सेस[i] की ऊंचाई के बराबर है या नेस्टेड[मिड] की चौड़ाई <= बॉक्सेस[i] की चौड़ाई, तो लेफ्ट := मिड + 1
- अन्यथा राइट := मिड - 1
- यदि लेफ्ट नेस्टेड के आकार के बराबर है, तो बॉक्सेस[i] को नेस्टेड के अंत में डालें
- अन्यथा नेस्टेड[लेफ्ट] की चौड़ाई और ऊंचाई को बॉक्सेस[i] के बराबर करें
- नेस्टेड का आकार लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; bool comp(const pair<int, int>& L, const pair<int, int>& R) { if (L.first == R.first) return L.second > R.second; return L.first < R.first; } int Rectangles(vector<pair<int, int>> &boxes) { int n = boxes.size(); sort(boxes.begin(), boxes.end(), comp); vector<pair<int, int> > nested; nested.push_back(boxes[n - 1]); for (int i = n - 2; i >= 0; --i) { int right = nested.size() - 1, left = 0; while (left <= right) { int mid = (right + left) / 2; if (nested[mid].first == boxes[i].first || nested[mid].second <= boxes[i].second) left = mid + 1; else right = mid - 1; } if (left == nested.size()) nested.push_back(boxes[i]); else { nested[left].second = boxes[i].second; nested[left].first = boxes[i].first; } } return nested.size(); } int main() { vector<pair<int, int>> boxes = {{30, 45}, {15,15}, {45,30},{60,75}}; cout << Rectangles(boxes); } इनपुट
{{30, 45}, {15,15}, {45,30},{60,75}} आउटपुट
2
