अद्वितीय टावरों की कुल ऊँचाई को अधिकतम करें: पायथन में लालची समाधान

Maximize the Total Height of Unique Towers (LeetCode 3301) में आपको हर टावर के लिए एक अधिकतम ऊँचाई दी जाती है। आपको हर टावर को एक धनात्मक पूर्णांक ऊँचाई देनी है जो उसकी अधिकतम से ज़्यादा न हो, और सभी ऊँचाइयाँ अलग-अलग हों। सबसे बड़ा संभव कुल योग लौटाइए, या अगर ऐसा संभव न हो तो -1। सॉर्ट करने के बाद एक greedy तरीका इसे O(n log n) में हल कर देता है।

समस्या

आपको एक array maximumHeight दिया गया है, जहाँ maximumHeight[i] बताता है कि टावर i की अधिकतम ऊँचाई क्या हो सकती है। height[i] ऐसे चुनिए कि:

• 1 <= height[i] <= maximumHeight[i]
• सभी height[i] मान अलग-अलग हों

अधिकतम संभव योग लौटाइए, या अगर कोई मान्य असाइनमेंट मौजूद न हो तो -1।

उदाहरण:

विचार

कुल योग बड़ा बनाने के लिए आप चाहेंगे कि हर टावर जितना हो सके उतना ऊँचा हो। ऊँचाइयाँ अलग-अलग होनी चाहिए, तो क्रम के बारे में सोचिए: सबसे ऊँची अनुमत ऊँचाई वाले टावर को सबसे बड़ा मान मिलना चाहिए, उसके बाद वाले को उससे छोटा सबसे बड़ा मान, और इसी तरह आगे।

1. maximums को घटते क्रम में सॉर्ट कीजिए।
2. पहले टावर को उसकी पूरी अधिकतम ऊँचाई दीजिए।
3. हर अगले टावर के लिए min(उसकी अधिकतम, पिछली ऊँचाई - 1) असाइन कीजिए।
4. अगर असाइन की गई ऊँचाई 0 या उससे नीचे चली जाए, तो कोई मान्य असाइनमेंट नहीं है, इसलिए -1 लौटाइए।
5. ऊँचाइयों को जोड़ दीजिए।

def maximum_total_sum(maximum_height):
    total = 0
    limit = float("inf")
    for m in sorted(maximum_height, reverse=True):
        h = min(m, limit - 1)
        if h <= 0:
            return -1
        total += h
        limit = h
    return total

[2,3,4,3] पर trace: घटते क्रम में सॉर्ट करने पर [4,3,3,2] मिलता है। ऊँचाइयाँ: 4, फिर min(3, 3) = 3, फिर min(3, 2) = 2, फिर min(2, 1) = 1। योग 10 है।

Greedy क्यों काम करता है

इसे exchange argument से समझा जा सकता है। मान लीजिए किसी optimal हल में बड़ी अधिकतम ऊँचाई वाले टावर को छोटी अधिकतम ऊँचाई वाले टावर से कम ऊँचाई मिली है। इन दोनों ऊँचाइयों को आपस में बदल देने पर दोनों अपनी-अपनी सीमा के अंदर ही रहती हैं, क्योंकि बड़ी अधिकतम ऊँचाई वाला टावर वह कोई भी मान ले सकता है जो छोटे वाले ने लिया था, और योग में कोई बदलाव नहीं होता। इसलिए कोई न कोई optimal हल ऐसा होता है जिसमें ऊँचाइयाँ सॉर्ट किए गए maximums के उसी क्रम में असाइन होती हैं।

एक बार क्रम तय हो जाने पर, हर टावर अपनी अधिकतम ऊँचाई से ज़्यादा ऊँचा नहीं हो सकता, और अपने से पहले वाले टावर की ऊँचाई से एक कम से ज़्यादा ऊँचा नहीं हो सकता। ठीक उसी ऊपरी सीमा को लेना सबसे अच्छा है: कम ऊँचाई अभी योग घटा देगी, और आगे के टावरों में भी कोई मदद नहीं करेगी, क्योंकि उनकी ऊपरी सीमाएँ इसी ऊँचाई पर निर्भर करती हैं, तो इसे कम करने से उनकी सीमाएँ भी कम ही होंगी।

मैंने इस कोड को 2,000 random छोटे arrays पर सभी असाइनमेंट की brute-force खोज से भी जाँचा, और जवाब मेल खाए।

Complexity

• Time: O(n log n), जिसमें सॉर्टिंग का ही दबदबा है। लूप O(n) है।
• Space: अगर आप जगह पर ही सॉर्ट करते हैं तो O(1) अतिरिक्त, या सॉर्ट की गई copy के लिए O(n)।

दूसरा नज़रिया: मानों की गिनती

-1 वाले मामले को देखने का एक और तरीका: सॉर्ट किए गए maximums m1 >= m2 >= ... >= mn के साथ, कोई मान्य असाइनमेंट तभी मौजूद होता है जब हर i के लिए i-वाँ सबसे बड़ा maximum कम से कम n - i + 1 हो, क्योंकि आपको उसके बराबर या उससे कम पर उतने ही अलग-अलग धनात्मक मान चाहिए। लूप चलते-चलते यही जाँच करता है।

Edge cases

Java या C++ में, जब बहुत सारे टावरों की maximums बड़ी हों तो कुल योग 32 bits से ज़्यादा हो सकता है, इसलिए long इस्तेमाल कीजिए।

इंटरव्यू में इसे कैसे समझाएँ

1. constraints दोबारा बताइए, -1 वाले मामले सहित।
2. कहिए कि आप ऊँचे टावर चाहते हैं जिनकी ऊँचाइयाँ अलग-अलग हों, इसलिए सबसे बड़ी maximum से नीचे की ओर प्रोसेस कीजिए।
3. नियम बताइए: हर ऊँचाई अपनी maximum और पिछली ऊँचाई से एक कम — इन दोनों में से जो छोटी हो, वही होती है।
4. कारण समझाइए: टावरों के बीच ऊँचाइयाँ बदलने से फ़ायदा नहीं होता, और हर चुनाव सबसे बड़ा संभव होता है।
5. complexity और overflow वाली बात बताइए।
6. [2,2,1], एक element, और सभी बराबर मानों के साथ टेस्ट कीजिए।

संबंधित अभ्यास

ऐसी ही greedy और sorting वाली समस्याओं में Assign Cookies और Minimum Number of Arrows to Burst Balloons शामिल हैं। अभ्यास को व्यवस्थित करने के तरीके के लिए हमारा Blind 75 study plan और AI LeetCode tutor guide देखिए, और review routines के लिए coding interview assistant guide देखिए।

अभ्यास करते समय exchange argument ज़ोर से बोलकर समझाइए। एक mock interview transcript दिखाता है कि आपने कोई कारण दिया या सिर्फ़ कोड। किसी भी live assessment में AI tools को लेकर employer के नियमों का पालन कीजिए।