ধরুন আমাদের কাছে বদ্ধ ব্যবধানের দুটি তালিকা রয়েছে, এখানে প্রতিটি ব্যবধানের তালিকা জোড়াভাবে বিচ্ছিন্ন এবং সাজানো ক্রমে রয়েছে। আমরা এই দুটি ব্যবধান তালিকার ছেদ খুঁজে বের করতে পেরেছি।
আমরা জানি যে বদ্ধ ব্যবধান [a, b] কে <=b হিসাবে চিহ্নিত করা হয়। a <=x <=b সহ বাস্তব সংখ্যা x এর সেট। দুটি বদ্ধ ব্যবধানের ছেদ হল বাস্তব সংখ্যার একটি সেট যা হয় খালি, অথবা একটি বন্ধ ব্যবধান হিসাবে উপস্থাপন করা যেতে পারে।
সুতরাং যদি ইনপুট হয় A =[[0,2],[5,10],[13,23],[24,25]] এবং B =[[1,5],[8,12],[ 15,24],[25,27]], তাহলে আউটপুট হবে [[1,2],[5,5],[8,10],[15,23],[24,24],[25 ,25]]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
res একটি তালিকা তৈরি করুন, I :=0 এবং j :=0
সেট করুন -
intersect() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি a এবং b −
লাগবে -
যদি a[0] <=b[0] এবং a[1]>=b[0] হয়, তাহলে সত্য ফেরত দিন,
-
অন্যথায় যখন b[0] <=a[0] এবং b[1]>=a[0], তখন সত্য ফেরত দিন, অন্যথায় মিথ্যা দিন
-
যখন আমি B এর সাইজ
-
যদি ছেদ করে(A[i], B[i])
-
তাপমাত্রা :=A[i, 0], B[j, 0] এর সর্বোচ্চ, A[i,1] এবং B[j, 1]
-
A[i,0] :=temp[1] + 1, B[j,0] :=temp[1] + 1
-
যদি A[i,0]> A[i,1] বা A[i,1] <=temp[0], তাহলে i 1 দ্বারা বাড়ান
-
যদি B[j,0]>B[j,1] বা B[j,1] <=temp[0]:তাহলে j বাড়ান 1
-
result.append(temp)
-
পরবর্তী পুনরাবৃত্তির জন্য এড়িয়ে যান
-
-
যদি A[i,0]> B[j, 1], তাহলে j 1 দ্বারা বাড়ান, অন্যথায় i 1 দ্বারা বাড়ান
-
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution(object): def intervalIntersection(self, A, B): result = [] i,j = 0,0 while i < len(A) and j < len(B): if self.intersect(A[i],B[j]): temp = [max(A[i][0],B[j][0]),min(A[i][1],B[j][1])] A[i][0]=temp[1]+1 B[j][0] = temp[1]+1 if A[i][0] > A[i][1] or A[i][1] <= temp[0]: i+=1 if B[j][0]>B[j][1] or B[j][1] <= temp[0]: j+=1 result.append(temp) continue if A[i][0]>B[j][1]: j+=1 else: i+=1 return result def intersect(self,a,b): if a[0]<=b[0] and a[1]>=b[0]: return True if b[0]<=a[0] and b[1] >=a[0]: return True return False ob = Solution() print(ob.intervalIntersection([[0,2],[5,10],[13,23],[24,25]],[[1,5],[8,12],[15,24],[25,27]]))
ইনপুট
[[0,2],[5,10],[13,23],[24,25]] [[1,5],[8,12],[15,24],[25,27]]
আউটপুট
[[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]