পাইথনে দীর্ঘতম চেইন তৈরি করে এমন বাক্সের সংখ্যা খুঁজে বের করার প্রোগ্রাম?

ধরুন আমাদের কাছে বাক্সের একটি তালিকা আছে, এখানে প্রতিটি এন্ট্রির দুটি মান রয়েছে [শুরু, শেষ] (শুরু <শেষ)। একটির শেষ অন্যটির শুরুর সমান হলে আমরা দুটি বাক্সে যোগ দিতে পারি। আমাদের বাক্সের দীর্ঘতম চেইনের দৈর্ঘ্য খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি ব্লকের মত হয় =[ [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

• dic

  -এর সমস্ত মানের তালিকার সর্বাধিক ফেরত দিন

আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:

উদাহরণ

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