मान लीजिए कि हमारे पास N विभिन्न आयतों की चौड़ाई और ऊंचाई है; हमें एक को दूसरे में डालने के बाद बचे हुए आयतों की न्यूनतम संख्या ज्ञात करनी होगी। इसलिए, यदि W1 और W2 क्रमशः आयत R1 और R2 की चौड़ाई हैं। और H1 और H2 क्रमशः R1 और R2 की ऊंचाई हो, तो यदि W1
इसलिए, यदि इनपुट {{30, 45}, {15, 15}, {45, 30},{60, 75}} जैसा है, तो आउटपुट 2 होगा क्योंकि दूसरा आयत सम्मिलित करने के संभावित तरीकों में से एक है पहले वाले में और फिर उस आयत को चौथे में डालें। तीसरा और चौथा आयत बाकी है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
n :=बक्सों का आकार
सरणी बक्से को उनके आकार के आधार पर क्रमबद्ध करें
जोड़े के नेस्टेड सरणी को परिभाषित करें
नेस्टेड के अंत में बॉक्स [n - 1] डालें
इनिशियलाइज़ करने के लिए i :=n - 2, जब i>=0, अपडेट करें (i से 1 घटाएं), −
दाएं:=नेस्टेड का आकार
जबकि बाएँ <=दाएँ, करें:
मध्य:=(दाएं+बाएं)/2
यदि नेस्टेड की ऊंचाई [मध्य] बक्से की ऊंचाई के समान है [i] या नेस्टेड की चौड़ाई [मध्य] <=बक्से की चौड़ाई [i], तो -
बायां :=मध्य + 1
अन्यथा
दाएं:=मध्य - 1
यदि बाईं ओर नेस्टेड के आकार के समान है, तो -
नेस्टेड के अंत में बक्से [i] डालें
अन्यथा
नेस्टेड की चौड़ाई [बाएं] :=बक्सों की चौड़ाई[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
