मान लीजिए हमारे पास अंतराल का एक सेट है; हमें उन न्यूनतम अंतरालों की संख्या ढूंढनी है जिन्हें हटाया जाना चाहिए ताकि बाकी अंतराल गैर-ओवरलैपिंग हों। इसलिए यदि अंतराल [[8,10],[3,5],[6,9]] हैं, तो आउटपुट 1 होगा, क्योंकि हमें [6,9] को हटाना होगा ताकि बाकी सभी गैर-ओवरलैपिंग हों।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- n := सरणी का आकार
- यदि n 0 है, तो 0 लौटाएं
- count := 1
- अंतराल के अंत समय के आधार पर सरणी को सॉर्ट करें
- end := पहले अंतराल का अंत समय
- i को 1 से n-1 तक रेंज में
- यदि arr[i] का प्रारंभ समय >= end, तो
- end := arr[i] का अंत समय
- count को 1 से बढ़ाएं
- यदि arr[i] का प्रारंभ समय >= end, तो
- 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 = {{8,10},{3,5},{6,9}}; Solution ob; cout << (ob.eraseOverlapIntervals(v)); } इनपुट
{{8,10},{3,5},{6,9}} आउटपुट
1
