ধরুন আমাদের অন্তরের একটি তালিকা আছে। এই তালিকার ব্যবধানে [i] আছে [শুরু, শেষ] মান। আমাদের খুঁজে বের করতে হবে যে ব্যবধানের সংখ্যাটি অন্য একটি ব্যবধান দ্বারা রয়েছে। যদি এমন একটি ব্যবধান থাকে যা একাধিক অন্যান্য ব্যবধান দ্বারা ধারণ করে থাকে যা শুধুমাত্র একবার গণনা করা উচিত। একটি ব্যবধান [s0, e0] আরেকটি ব্যবধান [s1, e1] এর মধ্যে থাকে যখন s0 ≤ s1 এবং e0 ≥ e1 হয়।
সুতরাং, যদি ইনপুটটি অন্তরের মত হয় =[[2, 6],[3, 4],[4, 7],[5, 5]], তাহলে আউটপুট হবে 2, কারণ [3, 4] এবং [ 5, 5] যথাক্রমে [2, 6] এবং [4, 7] ভিতরে রয়েছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- যদি ব্যবধান তালিকা খালি থাকে, তাহলে
- রিটার্ন 0
- সূচনা সময়ের উপর ভিত্তি করে ব্যবধান তালিকা বাছাই করুন, যখন শুরুর সময় একই হয়, শেষ সময়ের হ্রাসের ক্রমে সাজান
- end_mx :=-ইনফিনিটি
- উত্তর :=0
- ব্যবধানে প্রতিটি (শুরু, শেষ) জোড়ার জন্য, করুন
- যদি শেষ <=end_mx, তারপর
- উত্তর :=উত্তর + ১
- end_mx :=end_mx এবং শেষের সর্বোচ্চ
- যদি শেষ <=end_mx, তারপর
- উত্তর ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
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, 6],[3, 4],[4, 7],[5, 5]]
আউটপুট
2