मान लीजिए हमारे पास n वस्तुओं की एक सरणी है। प्रत्येक वस्तु की चौड़ाई W[i] है। हमें उन्हें पिरामिड के तरीके में व्यवस्थित करना है जैसे -
i-वें स्तर की कुल चौड़ाई (i+1)-वें स्तर से कम हो
i-वें स्तर में वस्तुओं की कुल संख्या (i+1)-वें स्तर से कम हो
उदाहरण के लिए, यदि चौड़ाई [40, 100, 20, 30] है, तो आउटपुट 2 होगा। शीर्ष स्तर 30 है, फिर निचला स्तर 20, 40 और 100।
इसे हल करने के लिए, हम लालची दृष्टिकोण का उपयोग करेंगे। विचार है कम चौड़ाई वाली वस्तुओं को शीर्ष पर रखना, अगली वस्तु को ठीक नीचे के स्तर पर रखना और इसी तरह। अधिकतम स्तरों की संख्या प्राप्त करने के लिए, दी गई सरणी को सॉर्ट करें और ऊपर से नीचे पिरामिड बनाने का प्रयास करें।
फिर सरणी के सबसे छोटे तत्व को ढूंढें जैसे सॉर्टिंग के बाद सरणी का पहला तत्व, इसे शीर्ष पर रखें। फिर इसके नीचे अधिक वस्तुओं और अधिक चौड़ाई वाले स्तरों का निर्माण करने का प्रयास करें।
उदाहरण
#include <iostream> #include <algorithm> using namespace std; int maxLevelPyramid(int objects[], int n) { sort(objects, objects + n); int ans = 1; int prev_w = objects[0]; int count_p = 1; int count_c = 0; int curr_w = 0; for (int i=1; i<n; i++){ curr_w += objects[i]; count_c++; if (curr_w > prev_w && count_c > count_p){ prev_w = curr_w; count_p = count_c; count_c = curr_w = 0; ans++; } } return ans; } int main() { int boxes[] = {40, 100, 20, 30}; int n = sizeof(boxes)/sizeof(boxes[0]); cout << "Max level of pyramid: " << maxLevelPyramid(boxes, n); } आउटपुट
Max level of pyramid: 2
