মনে করুন একটি সোর্টেড ডিজয়েন্ট ইন্টারভাল লিস্ট আছে, প্রতিটি ইন্টারভাল `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, ],]
