ধরুন আমাদের একটি ইন্টারভালের অ্যারে আছে, প্রতিটি ইন্টারভাল i-এর জন্য চেক করতে হবে কি এমন কোনো ইন্টারভাল j আছে যার স্টার্ট পয়েন্ট ইন্টারভাল i-এর এন্ডপয়েন্টের চেয়ে বড় বা সমান, যা বলা হয় j, i-এর "রাইট"-এ আছে। যেকোনো ইন্টারভাল i-এর জন্য, আমাদের ন্যূনতম ইন্টারভাল j-এর ইনডেক্স সংরক্ষণ করতে হবে, যা বোঝায় ইন্টারভাল j-এর ন্যূনতম স্টার্ট পয়েন্ট ইন্টারভাল i-এর জন্য "রাইট" রিলেশনশিপ বিল্ড করে। যদি ইন্টারভাল j না থাকে, তবে ইন্টারভাল i-এর জন্য -1 সংরক্ষণ করুন। এবং অবশেষে, প্রতিটি ইন্টারভালের সংরক্ষিত মান আউটপুট করুন একটি অ্যারে হিসেবে। উদাহরণস্বরূপ, ইনপুট [[3,4], [2,3], [1,2]] হলে আউটপুট হবে [-1, 0, 1], কারণ [3, 4]-এর জন্য কোনো রাইট ইন্টারভাল নেই, [2,3]-এর জন্য [3,4]-এর ন্যূনতম "রাইট" স্টার্ট পয়েন্ট, এবং [1,2]-এর জন্য [2,3]-এর ন্যূনতম "রাইট" স্টার্ট পয়েন্ট।
সমাধানের ধাপগুলো:
n := intervals array-এর সাইজ, সাইজ n-এর একটি ret অ্যারে তৈরি করুন এবং -1 দিয়ে ফিল করুন, একটি map m তৈরি করুন
i = 0 থেকে intervals-এর সাইজ পর্যন্ত লুপ চালান
যদি intervals[i, 0] m-এ থাকে, তবে পরবর্তী ইন্টারভালে যান
m[intervals[i, 0]] := i + 1
i = n – 1 থেকে i >= 0 পর্যন্ত লুপ চালান
it := সেই কি-ভ্যালু পয়েন্টার যেটির সবচেয়ে ছোট কি কিন্তু intervals[i, 1]-এর চেয়ে ছোট নয়
যদি it-এর ভ্যালু 0 হয়, তবে পরবর্তী ইটারেশনে যান
ret[i] := it-এর ভ্যালু – 1
ret রিটার্ন করুন
উদাহরণ (C++)
নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে −
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> findRightInterval(vector<vector<int>>& intervals) { int n = intervals.size(); vector <int> ret(n, -1); map <int, int> m; for(int i = 0; i < intervals.size(); i++){ if(m.count(intervals[i][0])) continue; m[intervals[i][0]] = i + 1; } for(int i = n - 1; i >= 0; i--){ map <int, int> :: iterator it = m.lower_bound(intervals[i][1]); if(it->second == 0) continue; ret[i] = it->second - 1; } return ret; } }; main(){ vector<vector<int>> v = {{3,4},{2,3},{1,2}}; Solution ob; print_vector(ob.findRightInterval(v)); }
ইনপুট
[[3,4],[2,3],[1,2]]
আউটপুট
[-1,0,1]
