পাইথনে ইন্টারভালের তালিকা থেকে সবচেয়ে লম্বা মার্জড ইন্টারভাল বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে একটি ইন্টারভালের তালিকা আছে যেটি [start, end] ফর্মে। আমাদের কাজ হল ওভারল্যাপিং ইন্টারভালগুলো মার্জ করে সবচেয়ে লম্বা ইন্টারভাল বের করা।

উদাহরণস্বরূপ, যদি ইনপুট হয় [[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]], তবে আউটপুট হবে 9, কারণ মার্জ করার পর [1, 9] ইন্টারভাল পাওয়া যায় যেটির দৈর্ঘ্য ৯।

• intervals তালিকাটি সর্ট করুন।
• union := intervals[0] (প্রথম ইন্টারভাল)
• best := union[1] - union[0] + 1
• প্রতিটি s, e এর জন্য intervals[1:]-এ:
  • যদি s <= union[1] হয়, তবে union[1] := max(union[1], e)
  • অন্যথায়, union := [s, e]
  • best := max(best, union[1] - union[0] + 1)
• best রিটার্ন করুন।

class Solution:
    def solve(self, intervals):
        intervals.sort()
        union = intervals[0]
        best = union[1] - union[0] + 1
        for s, e in intervals[1:]:
            if s <= union[1]:
                union[1] = max(union[1], e)
            else:
                union = [s, e]
            best = max(best, union[1] - union[0] + 1)
        return best

ob = Solution()
intervals = [[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]
print(ob.solve(intervals))

[[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]

9