k दिनों में स्काईडाइवर्स के लिए न्यूनतम क्षमता वाला विमान ज्ञात करने का पायथन प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है जहां प्रत्येक मान स्काईडाइव करने के लिए एक साथ इच्छुक लोगों के समूह को दर्शाता है। और हमारे पास एक और मान k है जो दर्शाता है कि वे कितने दिनों में स्काईडाइविंग के लिए आवेदन कर सकते हैं। हमें विमान की न्यूनतम क्षमता ढूंढनी है जो सभी अनुरोधों को k दिनों के भीतर पूरा करने में सक्षम हो। अनुरोधों को दिए गए क्रम में पूरा किया जाना चाहिए और एक विमान दिन में केवल एक बार उड़ सकता है।

उदाहरण के लिए, यदि इनपुट nums = [16, 12, 18, 11, 13], k = 3 है, तो आउटपुट 28 होगा, क्योंकि 28-व्यक्ति वाला विमान दिए गए अनुरोधों को [16, 12], [18], [11, 13] में समूहित कर सकता है।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

यदि nums खाली है, तो
- 0 लौटाएं
start := nums का अधिकतम, end := nums के सभी तत्वों का योग
जब तक start < end, करें
- mid := (start + end) / 2
- days := 1, temp := 0
- प्रत्येक num के लिए nums में, करें
  - यदि temp + num > mid, तो
    - days := days + 1
    - temp := num
  - अन्यथा,
    - temp := temp + num
- यदि days > k, तो
  - start := mid + 1
- अन्यथा,
  - end := mid
start लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

class Solution:
    def solve(self, nums, k):
        if not nums:
            return 0
        start, end = max(nums), sum(nums)
        while start < end:
            mid = (start + end) // 2
            days = 1
            temp = 0
            for num in nums:
                if temp + num > mid:
                    days += 1
                    temp = num
                else:
                    temp += num
            if days > k:
                start = mid + 1
            else:
                end = mid
        return start

ob = Solution()
nums = [16, 12, 18, 11, 13]
k = 3
print(ob.solve(nums, k))

इनपुट

[16, 12, 18, 11, 13], 3