পাইথনে বক্স চেইন থেকে সর্বাধিক দৈর্ঘ্যের চেইন বের করার প্রোগ্রাম

ধরা যাক বক্সের একটি লিস্ট রয়েছে, যেখানে প্রতিটি এন্ট্রির দুটি মান [start, end] (এখানে start < end) রয়েছে। দুটি বক্স জোড়া দেওয়া যায় যদি একটির end অন্যটির start-এর সাথে সমান হয়। আমাদের বক্সগুলোর সর্বাধিক দৈর্ঘ্যের চেইন বের করতে হবে।

উদাহরণ

ইনপুট: blocks = [[4, 5], [5, 6], [4, 8], [1, 2], [2, 4]]

আউটপুট: 4

ব্যাখ্যা: চেইন হবে [1, 2], [2, 4], [4, 5], [5, 6]

সমাধানের ধাপসমূহ

1. যদি boxes খালি হয়, তবে 0 ফেরত দিন
2. boxes লিস্টটি সর্ট করুন
3. dic := একটি খালি ম্যাপ (ডিফল্টডিক্ট ব্যবহার করুন)
4. প্রতিটি start s এবং end e এর জন্য boxes-এ:
   • dic[e] := max(dic[e], dic[s] + 1)
5. 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