पायथन में सबसे लंबी श्रृंखला बनाने वाले बक्से की संख्या खोजने का कार्यक्रम?

मान लीजिए कि हमारे पास बक्सों की एक सूची है, यहाँ प्रत्येक प्रविष्टि के दो मान हैं [प्रारंभ, अंत] (प्रारंभ <अंत)। हम दो बक्सों को जोड़ सकते हैं यदि एक का अंत दूसरे के प्रारंभ के बराबर हो। हमें बक्सों की सबसे लंबी श्रृंखला की लंबाई ज्ञात करनी है।

इसलिए, यदि इनपुट ब्लॉक की तरह है =[ [4, 5], [5, 6], [4, 8], [1, 2], [2, 4]], तो आउटपुट 4 होगा, जैसा कि हम श्रृंखला बना सकते हैं:[1, 2], [2, 4], [4, 5], [5, 6]

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

• अगर बॉक्स खाली हैं, तो

  • वापसी 0

• सूची बक्सों को क्रमित करें

• dic :=एक खाली नक्शा

• बॉक्स में प्रत्येक प्रारंभ और अंत ई के लिए, करें

  • dic[e] :=अधिकतम dic[e] और dic[s] + 1

• डीआईसी के सभी मूल्यों की अधिकतम सूची लौटाएं

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

उदाहरण

import collections

class Solution:
   def solve(self, boxes):
      if not boxes:
         return 0
      boxes.sort()
      dic = collections.defaultdict(int)
      for s, e in boxes:
         dic[e] = max(dic[e], dic[s] + 1)
      return max(dic.values())

ob = Solution()
boxes = [
   [4, 5],
   [5, 6],
   [4, 8],
   [1, 2],
   [2, 4]
]
print(ob.solve(boxes))

इनपुट

[[4, 5],
[5, 6],
[4, 8],
[1, 2],
[2, 4] ]

आउटपुट

4