পাইথনে লক্ষ্য ব্যবধান মার্জ করে ব্যবধান খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের নন-ওভারল্যাপিং ব্যবধানের একটি তালিকা আছে। এই শেষ সময়ের উপর ভিত্তি করে সাজানো হয়. আমাদের আরেকটি ব্যবধান লক্ষ্য আছে, লক্ষ্য মার্জ করার পরে চূড়ান্ত ব্যবধান খুঁজুন যাতে বিরতিগুলি এখনও অ-ওভারল্যাপিং এবং সাজানো থাকে।

সুতরাং, যদি ইনপুটটি অন্তরের মত হয় =[[1, 15],[25, 35],[75, 90]], লক্ষ্য =[10, 30], তাহলে আউটপুট হবে [[1, 35], [ 75, 90]] প্রথম দুটি ব্যবধান হিসাবে [1, 15] এবং [25, 35] একত্রিত করা হয়েছে৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• iv

  এর শেষে লক্ষ্য সন্নিবেশ করান

• শুরুর সময়ের উপর ভিত্তি করে iv সাজান

• res :=প্রথম ব্যবধান সহ একটি নতুন তালিকা

• i :=1

• যখন আমি

  • যদি iv[i] <=res এর শেষ ব্যবধানের শেষ সময় শুরু হয়, তাহলে

    • res এর শেষ ব্যবধানের শেষ সময় =সর্বাধিক (res এর শেষ ব্যবধানের শেষ সময় এবং iv[i] এর শেষ সময়)

  • অন্যথায়,

    • res এর শেষে iv[i] সন্নিবেশ করুন

  • i :=i + 1

• রিটার্ন রিটার্ন

উদাহরণ (পাইথন)

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

class Solution:
   def solve(self, iv, target):
      iv.append(target)
      iv.sort(key=lambda x: x[0])
      res = [iv[0]]
      i = 1
      while i < len(iv):
         if iv[i][0] <= res[-1][1]:
            res[-1][1] = max(res[-1][1], iv[i][1])
         else:
            res.append(iv[i])
         i += 1
      return res
ob = Solution()
intervals = [
   [1, 15],
   [25, 35],
   [75, 90]
]
target = [10, 30]
print(ob.solve(intervals, target))

ইনপুট

[[1, 15],[25, 35],[75, 90]], [10, 30]

আউটপুট

[[1, 35], [75, 90]]