ধরা যাক আমাদের অসংযোগ ব্যবধানের একটি সাজানো তালিকা আছে, প্রতিটি ব্যবধানের ব্যবধান[i] =[a, b] x সংখ্যার সেটকে প্রতিনিধিত্ব করে যেমন a <=x
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- manipulate2() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি ম্যাট্রিক্স a এবং একটি অ্যারে y গ্রহণ করবে
- x :=ম্যাট্রিক্স a এর শেষ সারি, তারপর a থেকে শেষ সারি মুছে ফেলুন
- z :=x
- x[0] :=y[1], z[1] :=y[0]
- যদি z[0] − z[1] হয়, তাহলে a-তে z যোগ করুন
- যদি x[0] − x[1], তাহলে x ঢোকান a
- প্রধান পদ্ধতিটি ম্যাট্রিক্স এবং একটি অ্যারে টি নিয়ে যাবে
- একটি ম্যাট্রিক্স উত্তর সংজ্ঞায়িত করুন এবং n :=ম্যাট্রিক্সে সারির সংখ্যা
- আমি 0 থেকে n –
- পরিসরে
- উত্তরগুলিতে [i] সন্নিবেশ করুন
- a :=a, b :=t এর শেষ সারি
- যদি a[0]> b[0], তাহলে a এবং b অদলবদল করুন
- যদি a এবং b ছেদ করে, তাহলে manipulate2(ans, t) কল করুন
- উত্তর ফেরত দিন
উদাহরণ(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, ],]