पायथन में बॉक्स की सबसे लंबी श्रृंखला की लंबाई ढूंढने का प्रोग्राम

बॉक्स की सूची दी गई है जहां प्रत्येक बॉक्स [start, end] (start < end) द्वारा दर्शाया गया है। दो बॉक्स जुड़ सकते हैं यदि एक का अंत दूसरे के शुरू के बराबर हो। सबसे लंबी श्रृंखला की लंबाई ढूंढें।

उदाहरण

इनपुट: boxes = [[4, 5], [5, 6], [4, 8], [1, 2], [2, 4]]

आउटपुट: 4

श्रृंखला: [1, 2] → [2, 4] → [4, 5] → [5, 6]

एल्गोरिदम (डायनामिक प्रोग्रामिंग + हैश मैप)

1. यदि सूची खाली है, तो 0 वापस करें।
2. बॉक्स को start के आधार पर सॉर्ट करें (फिर end के आधार पर)।
3. एक डिक्शनरी dp बनाएं जहां dp[end] = end पर समाप्त होने वाली सबसे लंबी श्रृंखला की लंबाई।
4. प्रत्येक बॉक्स (s, e) के लिए:
   • dp[e] = max(dp[e], dp[s] + 1)
5. dp के सभी मानों में से अधिकतम वापस करें।

पायथन कार्यान्वयन

import collections

class Solution:
    def solve(self, boxes):
        if not boxes:
            return 0
        boxes.sort()  # start के अनुसार सॉर्ट
        dp = collections.defaultdict(int)
        for s, e in boxes:
            dp[e] = max(dp[e], dp[s] + 1)
        return max(dp.values())

# परीक्षण
ob = Solution()
boxes = [[4, 5], [5, 6], [4, 8], [1, 2], [2, 4]]
print(ob.solve(boxes))  # आउटपुट: 4

व्याख्या

• dp[s] उस बिंदु तक की सबसे लंबी श्रृंखला देता है जहां एक बॉक्स समाप्त होता है।
• नया बॉक्स (s, e) उस श्रृंखला को बढ़ाकर e तक पहुंचाता है।
• सॉर्टिंग सुनिश्चित करता है कि जब हम (s, e) प्रोसेस करते हैं, तो dp[s] पहले से ही अंतिम मान रखता है।

समय जटिलता

• सॉर्टिंग: O(n log n)
• DP लूप: O(n)
• कुल: O(n log n)
• स्थान: O(n)