ধরুন, আমাদের একটি ইন্টারভাল সেট দেওয়া হয়েছে যাতে প্রতিটি ইন্টারভাল (a, b) আকারে থাকে। এখানে a হলো একটি ইভেন্টের শুরু করার সময় এবং b হলো শেষ করার সময়। আমাদের কাজ হলো যাচাই করা যে এই সেটের মধ্যে কোনো ইন্টারভাল অন্য কোনো ইন্টারভালকে সম্পূর্ণ ওভারল্যাপ করে কিনা। যদি ওভারল্যাপ থাকে তবে True ফেরত দিন, অন্যথায় False।
যেমন, ইনপুট [(4,6), (10,12), (7,9), (13,16)] হলে আউটপুট হবে False। আর ইনপুট [(4,6), (4,9), (7,11), (5,8)] হলে আউটপুট হবে True।
সমাধানের ধাপসমূহ
- ইন্টারভাল লিস্টটি সর্ট করুন।
- লুপ চালান i = 1 থেকে লিস্টের সাইজ পর্যন্ত:
- যদি
intervals[i][1] <= intervals[i-1][1]হয়, তবে True ফেরত দিন।
- যদি
- লুপ শেষ হলে False ফেরত দিন।
উদাহরণ কোড
def solve(intervals):
intervals.sort()
for i in range(1, len(intervals)):
if intervals[i][1] <= intervals[i-1][1]:
return True
return False
intervals = [(4,6),(10,12),(7,9),(13,16)]
intervals2 = [(4,6), (4,9), (7,11), (5,8)]
print(solve(intervals))
print(solve(intervals2))
ইনপুট
[(4,6),(10,12),(7,9),(13,16)] [(4,6), (4,9), (7,11), (5,8)]
আউটপুট
False True
