ইন্টারভালের একটি তালিকা দেওয়া আছে যেখানে interval[i] = [start, end]। অন্য একটি ইন্টারভাল দ্বারা সম্পূর্ণরূপে সমाहিত ইন্টারভালের সংখ্যা বের করতে হবে। একাধিক ইন্টারভাল দ্বারা সমাহিত হলে একবারই গুনতে হবে। [s0, e0] ইন্টারভাল [s1, e1]-এর ভেতরে থাকে যদি s0 ≥ s1 এবং e0 ≤ e1।
সমস্যা উদাহরণ
ইনপুট: intervals = [[2, 6], [3, 4], [4, 7], [5, 5]]
আউটপুট: 2
ব্যাখ্যা: [3, 4] ইন্টারভাল [2, 6]-এর ভেতরে এবং [5, 5] ইন্টারভাল [4, 7]-এর ভেতরে।
সমাধানের পদ্ধতি (সর্টিং + ট্র্যাকিং)
- যদি intervals খালি হলে ০ রিটার্ন করুন
- ইন্টারভালগুলো সাজান: শুরু সময় অনুযায়ী ক্রমবর্ধমান, শুরু সময় সমান হলে শেষ সময় অনুযায়ী ক্রমঅবর্ধমান
end_mx = -inf,ans = 0- প্রতিটি (start, end) জোড়ার জন্য:
- যদি
end <= end_mxহলেans += 1(এই ইন্টারভাল আগের কোনো ইন্টারভালের ভেতরে) end_mx = max(end_mx, end)
- যদি
ansরিটার্ন করুন
পাইথন কোড
def solve(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: (x[0], -x[1]))
end_mx = float("-inf")
ans = 0
for start, end in intervals:
if end <= end_mx:
ans += 1
end_mx = max(end_mx, end)
return ans
intervals = [[2, 6], [3, 4], [4, 7], [5, 5]]
print(solve(intervals)) # আউটপুট: 2টেস্ট কেস
ইনপুট: [[2, 6], [3, 4], [4, 7], [5, 5]]
আউটপুট: 2
সময় জটিলতা: O(n log n) - সর্টিংয়ের জন্য।
স্থান জটিলতা: O(1) - অতিরিক্ত স্পেস।
