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