मान लीजिए हमारे पास ऊंचाई h और चौड़ाई w का एक आयताकार केक है, हमारे पास दो इंटीजर ऐरे horizontalCuts और verticalCuts भी हैं जहां horizontalCuts[i] केक के शीर्ष से i-वें क्षैतिज कट की दूरी दर्शाता है और इसी तरह, verticalCuts[j] केक के बाएं से j-वें ऊर्ध्वाधर कट की दूरी दर्शाता है।
हमें horizontalCuts और verticalCuts ऐरे में दिए गए प्रत्येक क्षैतिज और ऊर्ध्वाधर स्थिति पर काटने के बाद केक के टुकड़े का अधिकतम क्षेत्रफल ढूंढना है। उत्तर बड़ा हो सकता है, इसलिए इसे 10^9 + 7 मॉड्यूलो लौटाएं।
इसलिए, यदि इनपुट है h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
तो आउटपुट 4 होगा, क्योंकि उस छवि से हम दिए गए आयताकार केक को समझ सकते हैं।
लाल रेखाएं क्षैतिज और ऊर्ध्वाधर कट हैं। केक काटने के बाद, हरे रंग का केक का टुकड़ा अधिकतम क्षेत्रफल वाला है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक फ़ंक्शन mul() परिभाषित करें, जो a, b लेगा,
((a मॉड m) * (b मॉड m)) मॉड m लौटाएं
मुख्य विधि से हम h, w, एक ऐरे hh, एक ऐरे vv लेंगे,
hh और vv ऐरे को सॉर्ट करें
hh के पहले एलिमेंट को इंडेक्स 0 पर hh में डालें
h को hh के अंत में डालें
vv के पहले एलिमेंट को इंडेक्स 0 पर vv में डालें
w को vv के अंत में डालें
a := 0, b := 0
i := 1 से शुरू करें, जब i < hh का आकार, i बढ़ाते हुए, करें -
a := max(a, hh[i] - hh[i - 1])
i := 1 से शुरू करें, जब i < vv का आकार, i बढ़ाते हुए, करें -
b := max(b, vv[i] - vv[i - 1])
mul(a, b) लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; typedef long long int lli; class Solution { public: lli mul(lli a, lli b){ return ((a % mod) * (b % mod)) % mod; } int maxArea(int h, int w, vector<int>& hh, vector<int>& vv) { sort(hh.begin(), hh.end()); sort(vv.begin(), vv.end()); hh.insert(hh.begin(), 0); hh.push_back(h); vv.insert(vv.begin(), 0); vv.push_back(w); int a = 0; int b = 0; for (int i = 1; i < hh.size(); i++) { a = max(a, hh[i] - hh[i - 1]); } for (int i = 1; i < vv.size(); i++) { b = max(b, vv[i] - vv[i - 1]); } return mul(a, b); } }; main(){ Solution ob; vector<int> v = {1,2,4}, v1 = {1,3}; cout << (ob.maxArea(5,4,v,v1)); }इनपुट
5,4,{1,2,4}, {1,3}आउटपुट
4
