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

মনে করুন আমাদের একটি নন-ওভারল্যাপিং ইন্টারভ্যালের তালিকা আছে। এগুলো এন্ড টাইম অনুযায়ী সাজানো আছে। আমাদের আরেকটি ইন্টারভ্যাল target আছে, target মিলিয়ে ফাইনাল ইন্টারভ্যাল খুঁজে বের করতে হবে যাতে ইন্টারভ্যালগুলো এখনও নন-ওভারল্যাপিং এবং সাজানো থাকে।

উদাহরণস্বরূপ, যদি ইনপুট হয় intervals = [[1, 15],[25, 35],[75, 90]], target = [10, 30], তবে আউটপুট হবে [[1, 35], [75, 90]] কারণ প্রথম দুটি ইন্টারভ্যাল [1, 15] এবং [25, 35] মিলে যায়।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:

• target কে iv-এর শেষে যোগ করুন

• iv কে শুরু সময় অনুযায়ী সাজান

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

• i := 1

• যখন i < iv-এর আকার, করুন

  • যদি iv[i]-এর শুরু সময় res-এর শেষ ইন্টারভ্যালের এন্ড টাইমের চেয়ে কম বা সমান হয়, তবে

    • res-এর শেষ ইন্টারভ্যালের এন্ড টাইম = res-এর শেষ ইন্টারভ্যালের এন্ড টাইম এবং iv[i]-এর এন্ড টাইম-এর সর্বোচ্চ

  • অন্যথায়,

    • iv[i]-কে res-এর শেষে যোগ করুন

  • i := i + 1

• res রিটার্ন করুন

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

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:

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]]