ধরা যাক ইন্টারভালের একটি সংগ্রহ আছে; আমরা বাকি ইন্টারভালগুলোকে নন-ওভারল্যাপিং করতে কতগুলো ইন্টারভাল রিমুভ করতে হবে তার ন্যূনতম সংখ্যা বের করব। যদি ইন্টারভালগুলো হয় [[1,2], [2,3], [3,4], [1,3]], তবে আউটপুট হবে 1, কারণ [1,3] রিমুভ করলে বাকিগুলো নন-ওভারল্যাপিং হয়।
সমাধানের ধাপগুলো −
n := অ্যারের আকার
যদি n 0 হয়, তবে 0 রিটার্ন করব
count := 1
অ্যারেটি ইন্টারভালের এন্ড টাইম অনুযায়ী সর্ট করব
end := প্রথম ইন্টারভালের এন্ড ডেট
i = 1 থেকে n-1 পর্যন্ত
যদি arr[i]-এর স্টার্ট টাইম >= end হয়, তবে
end := arr[i]-এর এন্ড টাইম
count ১ বাড়াব
n - count রিটার্ন করব
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: static bool cmp(vector <int>& a, vector <int>& b){ return a[1] < b[1]; } int eraseOverlapIntervals(vector<vector<int>>& arr) { int n = arr.size(); if(!n)return 0; int cnt = 1; sort(arr.begin(), arr.end(), cmp); int end = arr[0][1]; for(int i = 1; i < n; i++){ if(arr[i][0] >= end){ end = arr[i][1]; cnt++; } } return n - cnt; } }; main(){ vector<vector<int>> v = {{1,2},{1,2},{1,2}}; Solution ob; cout << (ob.eraseOverlapIntervals(v)); }
ইনপুট
[[1,2],[1,2],[1,2]]
আউটপুট
2
