मान लीजिए हमारे पास डिस्जॉइंट इंटरवल्स की एक सॉर्टेड सूची है, प्रत्येक इंटरवल intervals[i] = [a, b] उन संख्याओं x के सेट को दर्शाता है जैसे कि a <= x < b। हमें intervals में किसी भी इंटरवल और toBeRemoved इंटरवल के बीच के इंटरसेक्शन को हटाना है। अंत में, हमें ऐसे सभी हटाने के बाद इंटरवल्स की सॉर्टेड सूची ढूंढनी है। यदि इनपुट इस प्रकार है - [[0,2], [3,4],[5,7]], और toBeRemoved := [1, 6], तो आउटपुट [[0, 2], [6,7]] होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- manipulate2() नामक एक मेथड परिभाषित करें, जो मैट्रिक्स a और एक ऐरे y लेगा
- x := मैट्रिक्स a की अंतिम पंक्ति, फिर a से अंतिम पंक्ति डिलीट करें
- z := x
- x[0] := y[1], z[1] := y[0]
- यदि z[0] - z[1], तो z को a में डालें
- यदि x[0] - x[1], तो x को a में डालें
- मेन मेथड मैट्रिक्स in और एक ऐरे t लेगा
- ans नामक एक मैट्रिक्स परिभाषित करें, और n := मैट्रिक्स in में पंक्तियों की संख्या
- i के लिए 0 से n - 1 तक की रेंज में
- in[i] को ans में डालें
- a := a की अंतिम पंक्ति, b := t
- यदि a[0] > b[0], तो a और b को स्वैप करें
- यदि a और b इंटरसेक्ट कर रहे हैं, तो manipulate2(ans, t) कॉल करें
- ans लौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित इम्प्लीमेंटेशन देखें -
#include <bits/stdc++.h> using namespace std; void print_vector(vector<vector<auto> > v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << "["; for(int j = 0; j <v[i].size(); j++){ cout << v[i][j] << ", "; } cout << "],"; } cout << "]"<<endl; } class Solution { public: bool isIntersect(vector <int> a, vector <int> b){ return max(a[0], a[1]) >= min(b[0], b[1]); } void manipulate2(vector < vector <int> > &a, vector <int> y){ vector <int> x = a.back(); a.pop_back(); vector <int> z = x; x[0] = y[1]; z[1] = y[0]; if(z[0] < z[1])a.push_back(z); if(x[0] < x[1])a.push_back(x); } vector<vector<int>> removeInterval(vector<vector<int>>& in, vector<int>& t) { vector < vector <int> > ans; int n = in.size(); for(int i = 0; i < n; i++){ ans.push_back(in[i]); vector <int> a; vector <int> b; a = ans.back(); b = t; if(a[0]>b[0])swap(a, b); if(isIntersect(a, b)){ manipulate2(ans, t); } } return ans; } }; main(){ vector<int> v2 = {1,6}; vector<vector<int>> v1 = {{0,2},{3,4},{5,7}}; Solution ob; print_vector(ob.removeInterval(v1, v2)); }इनपुट
[[0,2],[3,4],[5,7]] [1,6]
आउटपुट
[[0, 1, ],[6, 7, ],]
